Hash Table

해시테이블 관련 용어

• 해시테이블 : 자료구조
  - 해시함수를 사용해서 특정 해시값을 알아내고 그 해시값을 인덱스로 변환하여 키값과 데이터를 저장하는 자료구조이다.
  • 해시함수
    • 함수 : 어떤 값에 해당하는 다른값이 산출되는 계산식
      • 데이터를 효율적으로 관리하기 위한 목적으로
      • 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수
      • 어떤 값이 주어진 경우 -> 그 값을 대표하는 숫자를 계산하는 함수
      • 해시 함수의 계산으로 산출된 값을 해시값
  • 해시테이블 -> 탐색, 삽입, 삭제속도 O(1)
  • 해시테이블 -> 파이썬 구현 : 딕셔너리, 사전, dict
  • 해싱 : 해시함수를 사용해서 인덱스를 구성하는 과정
    - 데이터 -> 해시함수이 의해서 분류 -> 분류된 데이터 해시테이블 안에 들어가는 과정

해시탐색법의 특징

• 탐색 알고리즘
• 지금까지 배운 선형탐색, 이진탐색 -> (전제조건) 어떤 데이터가 어떤 요소에 들어있는지 전혀 모르는 상태에서 검색을 진행
• 선형탐핵
  • 배열의 처음부터 끝까지 차례대로 비교하여 원하는 데이터를 찾아내는 알고리즘
• 이진탐색
  • 정렬되어 있는 배열에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 알고리즘
• 해시탐색
  • 데이터의 내용과 저장한 곳의 요소를 미리 연결해 둠으로써 극히 짧은 시간안에 탐색할 수 있도록 고안된 알고리즘
• 데이터를 데이터와 같은 인덱스에 넣어두면 한 번에 찾을 수 있지 않을까?
  • 24 -> a[24]
  • 36 -> a[36]
  • 최소 -> 37개 크기를 가진 벼열이 준비
• 좀 더 효율적으로 배열 사용하기 위해서 -> 데이터에 일정한 계산을 실시 -> 결과값과 같은 인덱스를 가진 요소에 보관하는 방법
• 24 % 10 -> 4
• 36 % 10 -> 6
  0 1 2 3 4 5 6 7 8 9 -> 10개 크기의 배열
• 반드시 어떤 계산을 해야하는 법은 없다.