Hash 자료구조 - java

Hash 자료구조란?

---

• key와 Value 가 쌍을 이루는 자료구조
• key 탐색의 시간복잡도가 O(1) 이다.
• key 삭제의 시간복잡도가 O(1) 이다.
• key와 Value 삽입의 시간복잡도가 O(1) 이다.

  

Hash 자료구조의 경우 검색과 삽입, 삭제 연산을 엄청 빠르게 하는 자료구조라고 할 수 있다. 위에서 기술했듯이 상수시간에 데이터를 검색하는데, 이것은 Hash 자료구조의 특성 덕분이다. 

 Hash 자료구조에 Key 와 Value 를 삽입하려면, 우선 key에 해당하는 데이터를 Hash Function (해시 함수) 를 통해 Hash Code 로

변환한 뒤에, 자료구조 크기로 % 연산을 통해 해당 데이터를 저장할 index 를 구한다. 그리고 Value 를 해당 index 에 저장한다.

 

 

 

Hash Collision - 해쉬 충돌

---

어떤 데이터를 삽입하려고 할 때, 해쉬 함수에 의해 반환되는 hash code 에 이미 데이터가 존재하는 경우가 있다. 이런 경우를 Hash  Collision 이라고 하며, 이것을 해결하기 위한 방법이 존재한다.

 

 

• Chaining 
  • 해쉬 충돌이 일어날 경우, 데이터들을 링크드 리스트 형태로 연결한다.
  • 모든 key 값이 같은 Hash Code 를 가지는 최악의 경우, O(n) 의 시간복잡도를 가질 수 있다.
  • 데이터를 탐색할 때 key 에 대한 인덱스가 가리키고 있는 LinkedList 를 선형 검색하여, 해당 키에 대한 데이터를 반환한다.
• Open Addressing
  • 해쉬 충돌에 대해서 Linked List 와 같은 추가적인 메모리를 사용하지 않고, Hash Table 의 빈 공간을 사용하는 방법
  • 해쉬 충돌에 대비해 Hash Table 의 크기를 크게 잡아야 한다.
  • Linear Probing
    • 해쉬 충돌이 발생할 때 순차적으로 다음 인덱스를 탐색하여 빈 공간에 키와 데이터를 삽입하는 방식
    • 순차적으로 삽입하기 때문에 이 역시 최악의 경우 시간복잡도가 O(n) 이 될 수 있다.
  • Double Hashing
    • 충돌이 일어난 키를 다른 해시 함수로 계산하여 그 값을 현재 주소에 더하여 새 주소를 얻는 방식

 

Hash 의 단점

---

• 순서/ 관계가 있는 배열에는 어울리지 않는 자료구조이다.
• 데이터가 저장되기 전에 저장공간을 미리 생성해야 한다. 또한 해쉬 함수에 따라 해쉬 충돌이 자주 발생할 수 있으며, 만들어진 공간이 사용되지 않을 수 있어 메모리 낭비가 심할 수 있다.
• Hash Function 에 대한 의존도가 높다.