[자료구조 및 알고리즘] CH5. Map and Hash table

 

Map(Dictinary)이란?

• value와 unique key가 mapping되는 자료구조

Ordered map vs. Unordered map

• ordered map : key값이 정렬된 것 - balanced tree로 구현
• unordered map : key값이 정렬되지 않은 것 - hash table로 구현

Hashing이란?

• hash function을 통해 key value(hash key)를 table의 position으로 mapping시키는 것

Hash function을 고를 때 유의사항

• 계산에 드는 cost가 낮은 것(easy to compute)
• collision을 최소화하는 것
• hash table slot에 데이터를 균등하게 분포시키는 것(evenly distributed)

Hash에서 collision이란?

• hash function h가 서로 다른 key value에 대해 같은 position을 가리키는 것

Collision 해결책

• Open hashing(Separate Chaining)
• Closed hashing(Open Addressing)

Separate Chaining(Open hashing)이란?

• hash table의 각 slot을 linked list처럼 구현해 collision을 해결하는 방법(Hash table의 outside에 저장한다고 해서 "open hashing"이라 한다.)

Separate Chaining(Open hashing)

Open assressing(Closed hashing)이란?

• collision이 일어나면 hash table 내의 다른 비어있는 공간을 찾아 저장하는 방법(within the table에 저장한다 해서 "closed hashing"이라 한다.)
• 비어있는 공간을 찾는 방법 중 일부는 clustering으로 인해 비효율적이 될 수 있다.

Closed hashing에서 Probe sequence란?

• collision resolution에 따라 insertion할 때, 방문한 slot의 sequence
• Probing 방식은 probe function에 따른다(바로 다음 빈 공간을 찾는 linear probing, 임의의 빈 곳을 찾는 random probing 등...)

Hasing의 문제점인 Clustering이란?

• 각 slot이 선택될 확률이 정확히 동일하지 않아 데이터가 특정 범위의 공간에 몰리는 현상(Primary clustering)

Secondary clustering이란?

• collision이 발생하는 두 key가 같은 probe sequence를 갖는 것
• 해결법 : probe function이 original key value의 function이 되도록 설정

Double hashing(re-hashing)이란?

• collision이 발생하면 다시 한 번 hash function을 적용시키는 것

Hash table의 deletion에서 발생가능한 문제는?

• deletion으로 인한 unused space가 다음 번 searching에 방해가 되면 안된다.
• 주기적으로 hash table을 reorganize하거나 delete된 것을 표시하면 mark(tombstone)을 사용해 해결

Hash table delete시 발생할 수 있는 문제