해시 테이블
해시 테이블은 해시 함수와 배열을 같이 사용하는 자료 구조이다. key를 바로 인덱스로 사용하지 않고 해시 함수에 넣어서 리턴된 값을 인덱스로 사용하고 한 인덱스에 key와 value를 모두 저장한다. 저장한 데이터를 가지고 올 때도 해시 함수를 통해 리턴된 값으로 인덱스에 접근한다.
정리하면 해시 테이블은 아래와 같은 특징을 가지는 자료 구조이다.
- 고정된 크기의 배열을 만든다.
- 해시 함수를 이용해서 key를 원하는 범위의 자연수로 바꾼다.
- 해시 함수 결과 값 인덱스에 key - value 쌍을 저장한다.
해시 함수
특정 값을 원하는 범위의 자연수로 바꿔주는 함수이다. 해시 함수를 이용하면 키가 아무리 커도 항상 원하는 범위 사이의 자연수로 바꿀 수 있다. 조금 더 구체적인 조건을 살펴보면 아래와 같다.
- 하나의 해시 테이블에서 해시 함수는 항상 똑같은 결과가 나와야 한다. (결정론적)
- 결과 해시값이 어느 하나의 값으로 치우치지 않고 고르게 나와야 한다.
- 빠르게 계산할 수 있어야 한다.
