hash table / hashing

* hash table

🤗 반드시 알아야 할 자료구조 - 해시(Hash)에 대해서 알아보자!

 

🤗 파이썬에서 해시 테이블은 dictionary라는 자료구조를 통해 구현할 수 있다. dict() 클래스에 구현되어 있음. 

 

① list의 경우 숫자로만 indexing - 즉 자료 접근이 가능하지만, dictionary의 경우 key라는 특수한 index를 통해 접근 가능

② dictionary 함수 time complexity는 대부분 O(1) 매우 빠름

 

★ list vs. dictionary time complexity ★

operation	dictionary	list
get item	O(1)	O(1)
insert item	O(1)	O(1) ~ O(N)
update item	O(1)	O(1)
delete item	O(1)	O(1) ~ O(N)
search item	O(1)	O(N)

 

🤗 set() / dict() <집합과 맵> 내용 참조 포스팅

* hash function & hashing

🤗 hash function이란?

→ 임의 길이 데이터(input)를 "암호화된 고정 길이(output)"의 데이터로 매핑(전환)하는 함수

 

→ 출력되는 데이터는 모두 동일길이. 하지만 input되는 값들에 단 한 글자만 차이가 있어도 완전히 다른 결과가 출력

 

🤗  hash function과 hash table과의 연관성

 

→ 다양한 key값(hash func에서의 input들)을 hash func에 넣고 난 다음의 여러 output들인 hash들이 hash table의 index로 쓰이고, 우리가 정말로 원하는 해당 key에 대응하는 value는 hash table의 index에 대응하는 value로 구성된다.

→ 파이썬에서의 hash table은 dictionary를 뜻함.

 

🤗 그렇다면 hashing은?

→ 위 개념정리한 hash table에서 indexing, 즉 내가 원하는 value를 찾기 위해 key를 hash function에 넣는 과정 - 즉 hash function을 사용하는 과정을 hashing이라고 한다.

 

🤗 정리하자면, key를 hash function에 넣는 hashing output인 hash가 index가 되고, 이 index에 맞는, 즉 key에 대응하는 value 한 쌍 (key, value)가 hash table에 저장된다.

 

key → hash(index) → (key. value) 저장

* hash table ex)

🤗 위 예시 설명

→ stock_prices라는 dictionary - 즉 hash table이 있다

→ 'march 6'라는 key를 hash function을 통한 hashing 결과 index 9가 나왔고, index 9에 대응하는, 즉 'march 6'에 대응하는 value 310이 저장

* hash collision>

🤗 hash에서 중요한 건, 서로 다른 input의 key가 hash func를 거친 후 동일한 output(same hashes)으로 나온 경우, 이를 우리는 '해시 충돌(hash collision)'이라고 한다.

 

🤗 좋은 hash function

→ 좋은 해쉬 함수란, 개별적으로 서로 다른 input들이 hash function을 거친 결과 최대한 각각 다른 hash로 나오게 해주는, 즉 충돌을 최소화하는 함수를 말한다.

 

🤗 solutions

① seperate chaining

→ 충돌 발생 시 동일한 key에 다른 value들을 일종의 연결리스트로 연결해 충돌을 해결

② open addressing

→ 충돌 발생 시 옆 빈 공간을 찾아 나가 빈 공간에 들어가게 해 충돌을 해결

 

※ handling hash collision 별도 포스팅 예정

* exercises>

→ 백준 hashing 문제 모음 

 

→ 백준 hash를 사용한 집합과 맵 문제 모음 

 

---

* source1)  https://s1m0hya.tistory.com/27

* source2) https://woonys.tistory.com

* source3) https://realpython.com/python-hash-table/