파이썬 코딩테스트 스터디 5주차 #1 - 해시의 개념 및 함수

해시의 개념

 

이번 '해시' 챕터 설명은 살짝 개념이 모호했다.

 

주욱 그냥 읽어봤을때

 

키가 있으면 → 해시 함수를 겨치면 → 해시 테이블의 또 다른 키와 값을 쉽게 찾는다?

 

이 정도로 정리하면 될 것 같다.

 

해시 함수

 

해시 함수가 변환한 값은 인덱스로 활용해야 하므로

해시 테이블의 크기를 넘으면 안된다.

 

현재 해시 함수의 결과는 해시 테이블의 크기인 0 과 N-1 사이의 값  

이때 해시테이블의 인덱스와 값 부분을 버킷이라고 한다. 

코딩테스트 합격자 되기 : 파이썬 편 - 211page

 

코딩테스트 합격자 되기 : 파이썬 편 - 209page

해시 함수가 변환한 값의 충돌은 최대한 적게 발생해야함.

여기서 충돌이란이란,

서로 다른 두키에 대해 해시 함수를 거쳐서 나온 결과가 동일한 경우

 

 

 

 

 

자주 사용하는 해시 함수 알아보기

 

 

근데 사실 아래부터 이해가 안되기 시작...

나눗셈법

h(x) = x mod m

x는 키,  m은 주로 소수를 사용한다. 

 

 

곱셈법

나눗셈법은 때에 따라 큰 소수를 사용해야하는데 

큰 소수를 구하기가 쉽지 않다는 단점이 있다. 

h(x) = (((x*A) mod 1) * m)

m은 최대 버킷의 개수 , A는 황금비

* 황금비는 무한소수로 대략 1.6180339887.. 

이 책에서는 황금비의 소수부의 일부인 0.6183만 사용

 

  

문자열 해싱

 

....

 

 

그냥 이론은 여기까지...