자료구조 - Hash(Hash Table)

해시 테이블(Hash Table)

연관배열 구조(associative array)로 키(key)에 값(value)을 저장하는 자료구조이다.

• 연관배열 구조는
  1개의 key와 1개의 value가 1:1로 연관되어 있다.
  따라서 key를 이용하여 value를 도출할 수 있다.
• 연관배열 구조는 다음의 명령이 가능하다.
  • key와 value가 주어졌을 때, 연관 배열에 그 두 값(key & value)을 저장
  • key가 주어졌을 때, 연관되는 value를 얻음
  • key와 새로운 value가 주어졌을 때, 원래 키에 연관된 value를 새로운 value로 변경
  • key가 주어졌을 때, 그 key에 연관된 value를 제거

위의 명령은 해시테이블에서도 동일하게 적용이 된다.

해시 테이블의 구조

해시 테이블은 키(Key), 해시함수(Hash Function), 해시(Hash), 값(value), 저장소(Bucket, Slot)로 이루어져 있다.

• key는 해시함수를 통해 해시로 변경이 되며 해시는 value와 매칭되어 저장된다.

• 키(key)
  고유한 값; 해시 함수의 input이 된다. 다양한 길이의 값이 가능. 이 상태로 최종 저장소에 저장하면 각각의 길이만큼 저장소를 구성해야 하기 때문에 해시 함수로 값을 바꾸어 저장함으로써 공간의 효율성을 추구할 수 있다.
• 해시함수(Hash Function)
  키(key)를 해시(hash)로 바꿔준다. 다양한 길이를 가지고 있는 키(key)를 일정한 길이를 가지는 해시(hash)로 변경하여 저장소를 효율적으로 운영할 수 있도록 도와준다.
  (해시함수를 통해서 해시가 array와 같은 구조를 갖고있음에도 더 빠른 처리를 할 수 있게 해준다.)
  다만, 서로 다른 키(key)가 같은 해시(hash)가 되는 경우를 해시 충돌(Hash Collision)이라고 하는데, 해시 충돌을 일으키는 확률을 최대한 줄이는 함수를 만드는 것이 중요하다.
• 해시(Hash)
  해시 함수(Hash Function)의 결과물이며, 저장소(bucket, slot)에서 값(value)과 매칭되어 저장된다.
• 값(Value)
  저장소(bucket, slot)에 최종적으로 저장되는 값으로 키와 매칭되어 저장, 삭제, 검색, 접근이 가능해야 한다.

---

해시 자료구조는 시간복잡도가 O(1)이기 때문에 알고리즘 풀이에서 효율성측면에 상당부분 유리함을 가져다준다.
특히나 일반적으로 list에 담아서 처리하게 되는 경우가 많은데, 특별히 순서가 중요한 데이터가 아니라면 해시로 처리하는 것이 유리할 수 밖에 없다.
ex) LIST = [1, 2, 3, 4]
-> DICT = {1:True, 2:True, 3:True, 4:True}

Youtube
https://www.youtube.com/watch?v=Vi0hauJemxA

---

Reference

블로그 cyranocoding