해시(Hash)란 무엇인가?

HashMap을 사용하면서 Hash란 것을 사용하고 있었는데, 조금 더 자세히 알아볼 수 있는 시간이 된 것 같다.

---

해시(Hash) 

 - 데이터를 다루는 기법 중 하나로 검색과 저장이 아주 빠르게 진행

 - Key Value 값이 한쌍으로 존재하고, key의 값이 인덱스로 변환된다.

 - 키에 대한 해싱값을 구하는 과정을 hashing(해싱) 이라고 한다.

 - 시간복잡도는 O(1) 에 수렴

https://www.youtube.com/watch?v=xls6jEZNA7Y&t=5s

---

 

충돌(Collusion)

키에 대한 해시값이 같은 경우( 이미 해시 버킷이 사용중인 경우) 를 뜻한다.

같은 인덱스 끼리 덮어씌어지어 먼저 저장된 데이터는 지워진다

https://medium.com/shell-tharsis/hash-collision-5891d7dde54f

 

충돌을 해결하는 방법

충돌이 일어나는 이유는 해시알고리즘이 잘 짜여져 있지 않기 때문이다.

해시의 장점은 빠른 데이터 접근인데, 충돌이 많으면 최대 검색시간이 O(n) 이 되어버린다.

얼마나 잘 분배한 것에 따라 좋은 알고리즘으로 구분할 수 있다.

 

문자열은 무한한 값이지만, 해시코드는 정수값만 가질 수 있어, 결국은 충돌이 일어날 수 밖에 없다.

 

 

체이닝 : 연결리스트로 노드를 계속 추가해 나가는 방식

 

선형 탐사 : 정해진 고정 폭으로 옮겨 해시값의 중복을 피한다.

 

 

 

 

 

 

참고

https://power-overwhelming.tistory.com/42

[자료구조/알고리즘] 해시(Hash) 란?

https://runa-nam.tistory.com/84

해시(Hash) 란?

https://www.youtube.com/watch?v=Vi0hauJemxA 

 

https://www.youtube.com/watch?v=xls6jEZNA7Y&t=5s