해시테이블

해시 테이블해시 테이블(hash table)은 효율적인 탐색을 위한 자료구조로 키(key)를 값(value)에 대응시킨다. 해시 테이블을 간단히 구현하는 경우, 배열과 해시 함수(hash function)만 있으면 된다.객체와 키를 해시 테이블에 저장할 경우, 해시 함수가 키를 정수값으로 대응 시키는데, 이 정수 값이 배열의 첨자(index)로 쓰인다. 객체는 배열의 해당 첨자 위치에 저장된다.하지만.. 이것은 정상적으로 작동하지 않을 수 있다. 왜냐하면 해시 함수가 계산하는 모든 키 값이 유일(unique)해야 하기 때문이다. 해시함수 후에 나오는 결과가 동일한 결과가 나올 경우 우리는 이것을 충돌(collision)이라고 한다. 충돌(collision)을 피하려면 모든 키 값을 고려해서 배열을 극도로..