해시 테이블과 해시 함수

해시 테이블(Hash table)

• 키-값 쌍을 효율적으로 검색, 삽입 및 삭제할 수 있는 데이터 구조
• 링크드 리스트의 배열로 구현되며, 여기서 각 링크드 리스트는 배열의 동일한 인덱스에 해시되는 키-값 쌍을 저장한다.
• 배열의 인덱스는 키를 배열의 고유 인덱스에 매핑하는 해시 함수를 사용하여 계산된다.
• 고유 인덱스 간의 충돌이 일어나면 chaining, open addressing 등의 방법으로 해결한다.

해시 함수(Hash function)

• 키를 입력으로 받아 해시 코드라고 불리는 고정 크기의 출력을 생성하는 함수
• 해시 코드는 해시 테이블의 어레이로 인덱싱하는 데 사용된다.
• 해시 함수의 목표는 서로 다른 두 키가 동일한 해시 코드를 생성하는 충돌 횟수를 최소화하면서 각 키에 대해 고유한 해시 코드를 생성하는 것이다.
• 충돌은 성능 문제뿐만 아니라 키를 덮어쓸 경우 잠재적인 데이터 손실로 이어질 수 있기 때문에 해시 함수의 품질이 중요하다.

좋은 해시 함수

• 결정론적(Deterministic): 해시 함수는 호출될 때마다 동일한 키에 대해 동일한 해시 코드를 생성해야 한다.
• 균일성(Uniformity): 해시 함수는 충돌을 최소화하기 위해 키를 배열 전체에 고르게 분산시켜야 한다.
• 효율성(Efficiency): 해시 함수는 계산 속도가 빨라야 한다.