해시

[자료구조/C언어] Hash

1. Hash란?임의의 크기의 값을 고정된 크기의 값으로 매핑하는 데 이때 해시 함수를 사용한다.key 와 values 를 가진다.검색 속도를 O(1)으로 만들기 위해 사용된다.2. 좋은 Hash Function은?해시 함수는 원소들이 균일하게 분포될 수 있을 만큼 충분히 골고루 분포되어야 한다.– 해시 함수는 편향되지 않아야 한다.– 요소에 모든 비트를 사용해야 한다 범용 해시 함수– 𝑏 버킷이 있는 경우 ℎ (𝑥) = 𝑖 확률은 모든 버킷에 대해 1/𝑏 이다.(이러한 확률을 가지고 있어야 굿)– 요소 𝑥는 1/𝑏 확률로 모든 버킷 𝑖에 넣을 수 있다.Hash Function으로는 Mid-square, Division, and Folding을 사용한다. 2.1. Hash Function 종..