개발하는 리프터 꽃게맨입니다.

좋은 해쉬 함수가 뭔데? 자료구조에서의 해쉬 함수는 키 값을 이용해 해쉬 주소를 얻어낼 수 있는 함수를 뜻하며 이는 엄밀하게 정해져있는 것이 아니라, 프로그래머가 상황에 따라 재량껏 정의하여 사용합니다. 여기서 나쁜 해쉬 함수와 좋은 해쉬 함수는 엄연히 다릅니다. 좋은 해쉬함수가 되기위한 조건을 몇 가지 살펴보도록 하죠. 1) 좋은 해쉬 함수의 조건 (1) 해쉬 함수의 값이 해쉬 테이블 전체에 균일하게 분산되어야 한다. 해쉬에서는 키 값이 균일하게 분산되어 있을수록 좋습니다. 키 값이 균일하게 분산되다는 것이 곧 충돌이 적어짐을 뜻하죠. (2) 충돌 발생 빈도가 적어야 한다. (3) 연산이 빨라야 한다. 너무 연산량이 많은 해쉬의 경우에는 데이터 접근 속도가 느리기 때문에 좋은 해쉬함수라고 할 수 없습니..

선형조사법의 한계 closed hashing 인 선형조사법의 한계는 데이터 클러스터 현상입니다. 단순하게 말하면, 데이터가 한 곳에 몰려서 군집을 이룬다는 것이죠. 선형 조사법은 충돌 발생시 선형으로 빈공간을 탐색하기 때문에, 충돌이 발생한 지역 위주로 데이터가 몰릴 가능성이 높습니다. 이차조사법 및 이중해쉬는 closed hasing, open addressing 해쉬임과 동시에, 선형조사법의 클러스터 현상을 보완하는 해쉬 구조입니다. 이차조사법 1) 개요 이차조사법이 상당히 간단합니다. 그냥 선형조사법에 양념만 쳐주면 되죠. 이것이 선형조사법의 삽입 코드입니다. 충돌시 hashAddr +1, hashAddr +2, HashAddr +3... 이런 식으로 +1 씩 더해간다는 것을 알 수 있습니다. 이제..

https://powerclabman.tistory.com/58 (이전 글) 충돌 이슈 1) 개요 해쉬에서 충돌은 불가피합니다. 어떤 키값이 들어올지 예측하지 못하기 때문에 그리고 쓸데없는 메모리 공간을 차지하는 것을 막이 위해 해쉬 테이블은 제한된 공간을 가지고 있고 해쉬 주소는 해쉬 함수를 통해 만들어지는데 다른 키 값에 대해서 값은 해쉬 주소가 나오는 건 어쩔 수 없습니다. 해쉬 테이블의 크기가 M개가 존재한다고 했을때, 들어올 수 있는 데이터의 수는 M 이상 일 수 있기 때문에 충돌이 발생할 수 밖에 없는 것이죠. 사이즈 100의 해쉬 테이블에 30개의 데이터만 넣어도 돌 확률이 99%에 도달합니다. 그래서 기본적으로 충돌이 발생한다고 생각하고, 어떻게 충돌에 대처할 것 인가를 생각하는 것이 중요..