해시테이블

• 데이터를 (key, value) 쌍으로 저장하는 자료구조로 데이터를 검색할수 있다
• 검색시 key 값을 해시 함수를 통해 해시 값으로 바꾸고, 해시 값 으로 테이블에 접근하여 실제 데이터를 가져와 빠르게 접근이 가능하다.
• 해시
  • 임의의 크기의 데이터(key)를 고정된 크기의 데이터로 변환시킨 것
  • 해시테이블의 인덱스
• 해시 함수
  • key를 해시값, 해시 테이블의 인덱스로 변환시켜주는 것
  • key 값을 일정한 크기의 해시값으로 바꿔준다
• 충돌(collision)
  • 해시 함수로 해시 테이블의 크기는 물리적으로 한계가 있기 때문에 같은 해시 값을 같는 경우가 발생
  • 이처럼 해시 값이 같은 경우 충돌(collsion)이 발생
• 충돌 해결
  • Open Address 방식(개방주소법)
    • 해시 충돌이 일어나면 다른 공간을 찾아 저장하는 것
    • 최악의 경우 저장위치를 찾지 못하고 처음 위치로 올 수 있다.
    • Linear Probing : 순차적으로 비어있는 공간 탐색
    • Quadratic probing : 2차 함수로 공간 탐색
    • Double hashing probing  : 2차 해시 함수를 사용
    • 저장된 데이터 검색 시 해당 인덱스의 키값이 같지 않다면 다음 칸으로 이동해 검색
    • 해시 테이블에 연속적으로 데이터가 저장되므로 캐시 효율이 높음
    • 하지만 버킷 사이즈가 커지면 캐시 효율이 떨어짐
  • Separate Chaining 방식(분리연결법)
    • 연결리스트를 이용하여 해시 충돌이나면 해당 위치에 노드를 추가해가는 방식
    • 연결리스트로 추가해가기 때문에 메모리가 더 필요로함