해쉬 공부

해쉬: 키에 데이터를 저장하는 데이터 구조다.

key를 통해서 해쉬 테이블에서 value 값을 가져올 수 있어 속도가 매우 빠르다.

 

파이썬에서는 딕셔너리라는 타입이 있기 때문에 편리하고 해쉬를 구현할 필요가 없다.

 

해쉬(hash):임의 값을 고정길이로 변환한다.

해쉬 테이블 : 해쉬값에 대응되는 value값을 저장하고 있는 데이터 구조.

해싱 함수: 키값을 산술연산을 통해 해쉬값(해쉬주소)를 반환하는 함수

해쉬 값(해쉬주소): key값을 해싱함수에 연산해서 나온값. 해쉬테이블에 인덱스로 넣어 찾으면

value값을 얻을 수 있다.

슬롯: 한개의 데이터를 저장할 수 있는 공간

해쉬 로직 :

1)key값을 구한다. ( data에서 새로운 key값을 뽑아내던가, 원래의 데이터를 key값으로 하던가

2)key를 해슁함수에 넣어 해쉬값(해쉬주소)를 구한다.

3)해쉬값을 주소로 해쉬테이블의 슬롯에 value값을 넣는다.

 

해쉬 키를 데이터에서 뽑아서 해쉬 함수를 만들고, 해쉬 테이블의 해쉬함수인덱스(주소)로 value값11을 저장해보았다.

 

 

해쉬 장점

1.검색 속도가 빠르다

2.키 중복확인이 쉽다

 

단점:

1.저장공간이 더 많이 필요하다

2.충돌문제에 대한 대처가 필요하다. ( 개방해슁, 폐쇄해슁등)

 

용도 : 검색 ,저장 삭제 읽기가 빈번한 경우 , 캐쉬 구현시

 

충돌 해결 방법

1) chaining 기법(개방 해슁)

충돌시 링크드리스트를 이용해서 데이터를 추가로 뒤에 연결시켜서 저장

2) linear probling 기법(폐쇄 해슁)

충돌시 해당 hash address의 다음 address부터 맨처음 나오는 빈공간에 저장.

저장공간 활용도 높이려고

 

빈번한 충돌 개선 -> 해쉬 함수 재정의 및 해쉬 테이블 확장

 

시간 복잡도 

보통의 경우에는 O(N)이 나오지만, 충돌이 계속 발생하면 링크드리스트의 시간복잡도인 O(N)까지 나온다.

 

 

 

 

 

개방해슁

처음 리스트를 8개로 선언했는데 chaining 기법으로 1번째 인덱스에 2개의 원소가 들어가 있는것을 볼 수 있다.

 

 

폐쇄 해슁 linear probling

충돌시 이번에는 1번인덱스에서 0번 인덱스로 충돌이 회피된 것을 볼 수 있다.

 

개방해슁과 폐쇄해슁의 차이점

 

:

개방해슁은 충돌이 난 슬롯에서 내부에서 연결리스트로 연결하여 내부에서 연결한다면

폐쇄해슁은 충돌이 난 슬롯을 건너뛰면서 다른 인덱스에 값을 대입한다.

아래로 깊게 들어가냐 아니면 기존의 인덱스들을 활용하냐의 차이라고 생각한다.