- 일반적으로 많은 언어들이 기본 유형으로 내장되어있는 해시맵, 해시테이블이 존재한다.
- 배열가 마찬가지로 뭘 따로 할 필요가 없다..
- 해쉬 알고리즘?!? → 어떤것이 해싱 알고리즘으로써 좋은건지 알아본다.
- 해시 테이블에서 일어나는 충돌은 무엇인지? → 충돌을 해결하는 방법을 알아본다.
- 해시 테이블은 key-value로 저장하는 자료구조
- 해시 테이블의 키는 순서를 가지지 않는다.
<aside>
💡 해시 테이블은 값을 찾거나, 새로운 값을 추가하거나, 값을 제거하는데 아주 빠르다!
</aside>
- 파이썬 → 딕셔너리
- 자바스크립트 → 객체, 맵 ( 기본적으로 해시 테이블로 구현되어져 있다. )
- 자바, 고, 스칼라 → 맵
<aside>
💡 언어 마다 키워드는 다르지만, 기본적으로 해시 테이블로 구현되어져 있다.
</aside>
자바스크립트의 객체, 맵이 없다고 생각하고 직접 구현해 보자!
- 우리가 key-value로 저장할 방법이 필요하다면 ‘직접 만들어서 써야한다’.
- 실제로 해시 테이블이 어떻게 동작하는지 아는게 목적
- 해시 테이블을 구현하기 위해 배열을 사용할 것이다.
- 우리가 인덱스 값(key) ‘pink’를 숫자로 바꿔서 배열에 저장할 수 있는 방법을 찾아 보아야 한다.
- obj[’pink’] → 배열에 저장해야 하기 때문에
- hash function이 이 작업을 해준다. 해시 함수
- 해시 함수는 보통 암호 기술, 보안에 사용되기 때문에 뛰어난 해시 함수를 만들기 위해 아직도 노력하고 있다.
- 예를들어 hash function의 인자로 ‘pink’라는 string을 넣으면 항상 같은 숫자값을 return 해야한다.
- 그리고 해시 함수는 단방향 함수이다. string → 특정 number로 return 하지만, 거꾸로 특정 숫자를 돌려서 해당 string을 찾을 수는 없다.
좋은 Hash 함수의 기준