간단 하고 알 기 쉬 운 데이터 구조의 해시 표

Hash 시 계 는 해시 표 라 고도 부 르 며 산 목록 이 라 고도 부른다.해시 표 는 함수 맵 의 사상 에 따라 키: Value 방식 으로 데 이 터 를 저장 하 는 비교적 특수 한 데이터 구조 이다.해시 표 의 가장 큰 특징 은 찾 을 데 이 터 를 신속하게 찾 을 수 있 고 조회 시간 이 O (1) 에 가깝다 는 것 이다.
해시 표 의 설계 원리
만약 우리 가 한 조 의 데 이 터 를 가지 고 있다 면, 어떤 엔지니어 의 매년 수입 상황.

2017 -- 100000
2018 -- 130000
2019 -- 140000
2020 -- 200000

만약 에 우리 가 일반적인 링크 로 이런 데 이 터 를 저장 하면 2019 년 의 수입 상황 을 조회 할 때 링크 의 초기 노드 부터 전체 링크 를 옮 겨 다 니 며 2019 년 을 찾 은 후에 해당 하 는 데 이 터 를 꺼 내야 한다.이 검색 시간 복사 도 는 O (n) 입 니 다. 2 분 검색 을 사용 할 때 도 시간 복잡 도 는 O (logn) 입 니 다.만약 에 우리 가 연도, 즉 key 값 을 알 수 있다 면 해당 하 는 수입 데 이 터 를 직접 꺼 낼 수 있 고 시간 복잡 도 는 O (1) 이 며 데 이 터 를 해시 표 에 저장 하면 우 리 는 이런 검색 을 실현 할 수 있다.해시 표 의 원 리 는 복잡 하지 않다. 쉽게 말 하면 키 에 따라 저장 위 치 를 계산 한 다음 에 데 이 터 를 이 공간 에 넣 고 조회 할 때 도 키 에 따라 저장 위 치 를 계산 한 후에 해당 하 는 값 을 직접 꺼 내 는 것 이다.
해시 함수
Key 에 따라 저장 위 치 를 계산 하 는 계산 규칙 을 우 리 는 해시 함수 라 고 부 릅 니까? 아니면 이 예 를 들 어 우 리 는 가장 간단 한 해시 함수 H (x) = x 를 찾 습 니 다.

1.        2020   array[]
2.   H(x) = x       ，        。
   array[2017] = 100000
   array[2018] = 130000
   array[2019] = 140000
   array[2020] = 200000
3.   2019      ，  H(x) = x        ，      array[2019]

위의 이 예 에서 우 리 는 간단 한 해시 표를 실 현 했 지만 그 중에서 대량의 공간 이 낭비 되 고 길이 가 2020 인 배열 은 우 리 는 4 개의 공간 만 사용 했다 는 것 을 알 수 있다. 다음은 우 리 는 이 해시 표를 개량 했다.저장 할 데 이 터 를 관찰 함으로써 우 리 는 새로운 해시 함수 H (x) = x - 2000 을 선택 합 니 다.

1.        20   array[]
2.   H(x) = x - 2000       ，        。
   array[2017 - 2000] = array[17] = 100000
   array[2018 - 2000] = array[18] = 130000
   array[2019 - 2000] = array[19] = 140000
   array[2020 - 2000] = array[20] = 200000
3.   2019      ，  H(x) = x - 2000        ，      array[19]

이 예 에서 공간의 낭 비 는 최적화 전보 다 대폭 줄 어 든 것 을 볼 수 있다.이 를 통 해 알 수 있 듯 이 데이터 특징 에 따라 적당 한 표 크기 와 해시 함 수 를 선택 하 는 것 이 해시 표 라 는 데이터 구조 실현 의 관건 이다.
다음은 몇 가지 통용 되 는 해시 함 수 를 소개 한다.

     
                  。
H(x) = x % p
        s, p      s     

     
       
H(x) = a * x + b
            a=1,b=0   a=1,b=-2000

   
      18560 55632，  key     ，       
18 + 56 + 0 = 74 
55 + 63 + 2 = 120 -->> 20(     )
          ，         ，             

     
       ，                     。
333 * 333 = 110889 ->> 08
444 * 444 = 197136 ->> 71
        key 

     
               key   
1125699 1123399 1158299
        ，          ，             key 
256 233 582
        200
56 33 382

충돌 하 다.
해시 표 가 해결 해 야 할 문 제 는 충돌 이다. 해시 함 수 를 선택 한 후에 서로 다른 데이터 가 똑 같은 key 를 계산 할 수 있다. 예 를 들 어 H (x) = x% 5 라 는 알고리즘 은 6 과 11 이 모두 1 을 계산 하고 이때 충돌 이 발생 할 수 있다.충돌 을 해결 하지 않 으 면 해시 표 는 구축 할 수 없다.충돌 을 해결 하 는 방법 은 다음 과 같은 몇 가지 가 있다.

     
              ，       key          ，        ，      。

     
              
H(x) = x % 5
    : {5, 6, 8, 12, 11}
  Key: { 0, 1, 3, 2, 1}
     [0, 1, 2, 3, 4, 5, 6, 7 .....]
        [5, 6, 12, 8, 11]    11   ，     1         ，                  ，        ，      4     11

               ，              key   ，        。
                   

총결산
해시 표 는 빠 른 조회 수 요 를 해결 하 였 으 나 디자인 을 잘못 하면 상당 하지만 공간 낭 비 를 초래 할 수 있 으 므 로 실제 상황 에 따라 디자인 해 야 한다.