해쉬(Hash)

 

해쉬(Hash) : 자료의 검색과 저장을 빠르고 효과적으로 진행하기위한 데이터를 다루는 기법

 

해시함수(Hash function):  자료를 해쉬테이블에 저장할때, value 값을 특정 key로 치환하여 저장. 이때 쓰이는 함수를 해쉬함수라고 하고 division, mid-square, folding, integer 등의 여러 기법이 존재

 

충돌(collision) : 결국 해쉬테이블은 자료를 인덱스로 치환하여 저장하게되는데, 이 과정에서 다른해쉬값이 같은인덱스로 치환된다면, 인덱스가 겹치게 되는데 이를 충돌이라고 한다.

 

 

충돌해결법

 

1.선형조사법

 

 

 

 

 

 

 

 

 

 

 

 

2.이차조사법

 

선형조사법이랑 구현은 비슷하지만, 특정영역에 원소가 몰릴경우 그 영역을 더 빨리 벗어날 수 있음

 

 

 

 

 

 

 

3.랜덤조사법

 

뭐 이런것도 있나보다.

 

난수발생시켜서 ran배열에 저장후, s(i)값으로 이용한다.

 

 

 

 

 

 

 

4.체이닝

 

 

 

그냥 연결리스트형식으로써 같은인덱스에 때려박음