해시 테이블

1. 정의

• Key-Value 데이터:순서가 아닌 이미 알고있는 정보를 이용하여 저장된 데이터를 검색할 수 있는 자료구조
• 하나의 Key에는 하나의 Value만 있어야함
• 리스트의 개념은 순서대로 정보를 저장하고자 할 때 유용함
  => 배열은 인덱스(데이터의 순서에 해당)를 통해 접근하여 O(1) 시간복잡도를 가짐
• 해시 테이블 구조는 저장된 key를 통해 value값을 구하고자 할 때 유용함

2. 해시 테이블

해시함수: 특정값을 원하는 범위의 자연수로 바꿔주는 함수로 해시함수를 사용하면 Key값이 아무리 크더라도 원하는 범위의 자연수로 바꿔줄 수 있다.

• 내부적으로 해시함수, 배열 모두 사용하여 해시 테이블 자료구조 생성

1. 고정된 크기의 배열 생성
2. 해시 함수를 이용해 key를 원하는 범위의 자연수로 바꾼 후
3. 해시 함수 결과 값 인덱스에 key-value쌍을 저장

3. 해시 테이블 Chaining 개념

• 해시함수의 결과값이 동일한 인덱스를 반환한 경우 충돌이 발생
  

• 배열 인덱스에 링크드 리스트를 저장하여 충돌해결