해시 테이블

• 해시 함수

  임의의 길이의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 매핑 하는 함수.

  보통 입력값의 범위보다 출력값의 범위가 좁은 경우 많기 때문에 입력이 다름에도 동일한 값이 출력되는 경우 존재(비둘기 집의 원리)

  이런 충돌 제외하고 의도적으로 충돌 계산해낼 수 없어야 함

  파이썬의 경우 딕셔너리에 넣기 위해 해시 함수 구현해야 함

• 해시값

  해시 함수를 적용하여 나온 고정된 길이의 값

• 해시 테이블

  색인(index) 에 해시값을 사용하는 자료 구조

  정렬을 하지 않고 빠른 검색, 빠른 삽입 가능

  충분히 큰 공간 할당 후 해시 함수 이용하여 고유 색인 생성. 그리고 그 고유 색인과 맞는 위치에 데이터 저장

  해시 함수는 해시 값을 계산하는 비용이 기존 검색 알고리즘에 비해 훨씬 적고 뛰어나야 함.

  • 해시 값이 충돌하는 경우 발생하는 경우

    • 연결 리스트

      각각의 색인을 ‘연결 리스트’ 로 만들어 새로 입력이 될 때마다 같은 해시 가져도 색인이 연결 리스트로 구현되어 원하는 데이터 접근

      같은 해시값을 가진 데이터의 경우 연결 리스트로 ‘연결’

      기본적인 자료구조와 임의로 정한 간단한 알고리즘만 있으면 가능

      해시 테이블 구조의 원형이라 해시 테이블 하면 바로 이 방식

    • 오픈 어드레싱

      같은 해시 가져서 충돌하더라도 비어있는 곳에 넣어 원하는 데이터 접근

      충돌 일어나면 테이블 공간 내에 탐사 통해 빈 공간 찾아 해결

      모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장 없음

      • 선형 탐사

        충돌이 발생할 경우 해당 위치부터 순차적으로 탐사 하나씩 진행

        가장 가까운 다음 빈 위치에 새 키 삽입

      • 단점

        수용률이 일정량 넘어서게 되면 저장/조회 성능 점점 떨어짐

        정렬하지 않은 상태로 데이터 저장하기 때문에 정렬된 순서로 접근하는 것에 비해 리소스 많이 먹음

        순회 돌 시 무효한 값들이 많아 실제 데이터 개수만 순회하는 것보다 더 많은 비용 듦

        • 해결법

          리스트 자체 크기 키운 뒤 재배열 (비용이 많이 들어 실시간으로 빠르게 처리 하기 무리 있음)

          큰 리스트를 하나 더 만들어서 적당한 타이밍에 몇개씩 점진적으로 옮겨 다 옮기면 기존의 테이블 없애 확장(메모리 더 많이 사용)

          항목 수가 적을 떄 짧은(적은 비트 수) 해시와 작은 저장공간 사용하다가 충돌 잦아지면 비트수 1비트 늘리고 저장공간도 2배 늘림(분산 DB에서 데이터 일관성 유지하기 위해 사용)

요약

• 해시 함수는 임의의 길이를 갖는 임의의 데이터에 고정된 길이 데이터로 매핑하는 함수

• 해시 값은 해시 함수를 적용하여 나온 고정된 길이의 값

• 해시 테이블은 색인 에 해시값을 사용하는 자료 구조

• 해시 테이블의 해시 함수는 해시 값을 계산하는 비용이 기존 검색 알고리즘에 비해 훨씬 적고 뛰어나야 함

• 해시 테이블은 충돌 처리 방식에 따라 연결 리스트와 오픈 어드레싱으로 나뉨

• 연결 리스트는 같은 해시 값을 가진 색인을 ‘연결 리스트’ 만들어 원하는 데이터 접근

• 오픈 어드레싱은 같은 해시 가져서 충돌하면 비어있는 곳에 넣어 원하는 데이터 접근

• 오픈 어드레싱의 경우 모든 원소가 자신의 해기값과 일치하는 주소에 저장된다는 보장 없음

• 선형 탐사는 충돌이 진행될 경우 가장 가까운 빈 위치에 새 키 삽입 하는 방식

• 단점으로 수용률 일정량 넘어서면 성능 떨어져서 여러 해결법 존재