해시

 

해싱 (hashing)

• 데이터의 키 값을 간단한 함수를 사용해 변환한 값을 리스트의 인덱스로 사용하여 데이터를 리스트에 저장하는 절차로 공간 낭비를 줄이면서 키 값을 이용한 데이터 검색의 시간 복잡도를 가능하다면 O(1)로 유지하기 위해 사용.
• 해시 함수 (hash function) : 해싱에 사용되는 함수
• 해시 값 (hash value) : 해시 함수가 계산한 값 (=해시 주소)
• 해시 테이블 (hash table) : 데이터가 해시 값에 따라 저장된 구조
• 해시 함수를 통해 큰 키 공간을 작은 주소 공간으로 변환.
• python에서는 hash() 함수를 통해 해싱을 진행할 수 있다.

 

해시 테이블 (hash table)

• 해시 테이블 ht는 m개의 버킷(bucket) ht[0], ht[1], ht[2], ... , ht[m-1]으로 이루어지는 테이블이며, 각 버킷은 s개의 슬롯을 가질 수 있음.
• 0 ~ m-1 : 버킷, 인덱스, 해시 값
• 0 ~ s-1 : 슬롯, value 값
• 해싱은 서로 다른 키 값을 가지는 데이터가 같은 해시 값을 갖게 되는 경우 충돌이 발생하는데, 버킷이 가지는 슬롯 수보다 많이 충돌이 발생하게 되면 버킷에 더 이상 데이터를 저장할 수없는 오버플로우가 발생함. 

해시 테이블의 구조