해시 테이블 설명

내가 가장 좋아하는 데이터 구조 중 하나는 간단하고 강력하기 때문에 해시 테이블입니다.

키-값 쌍을 저장하는 효율적인 방법이므로 이전에 사용해 본 적이 있을 것입니다.

해시 테이블 구현 이면에는 연구할 가치가 있는 몇 가지 흥미로운 컴퓨터 과학 개념이 있으며, 이것이 바로 이 기사에서 우리가 할 일입니다!

버킷 및 해시 함수

해시 테이블의 기본 아이디어는 우리가 효율적으로 (O(1)에서 ) 키로 인덱싱된 데이터를 검색합니다.

간단히 복습하자면 다음은 Ruby에서 해시 테이블을 사용하는 것과 같습니다.

가격 ={ 사과:0.50, 아이스크림:3, 스테이크:10}

해시 테이블을 구현하려면 두 가지 구성 요소가 필요합니다.

• 테이블 항목을 저장할 장소
• 이 데이터 저장소 내의 특정 위치(색인)에 키/값 쌍을 할당하는 방법

즉, 배열과 해시 함수가 필요합니다.

단순 해시 함수 구현

해시 함수 해시 테이블의 중요한 구성 요소입니다.

이 함수는 키를 관련 값을 조회하거나 업데이트하는 데 사용할 수 있는 인덱스로 변환합니다.

이것이 일반 배열과 해시 테이블의 가장 큰 차이점입니다.

배열에서는 인덱스를 통해서만 값에 액세스할 수 있으며 인덱스는 숫자만 될 수 있습니다. 해시 테이블에서 키를 통해 값에 액세스하고 키는 무엇이든 가능 (문자열, 기호, 정수…) 해시 함수를 작성할 수 있는 한.

모든 문자를 ASCII 값으로 변환한 다음 더하여 문자열에 대한 간단한 해시 함수를 작성할 수 있습니다.

예시입니다 :

BUCKETS =32def 해시(입력) input.to_s.chars.inject(0) { |합계, 채널| 합계 + 채널 } % BUCKETSend

이 방법에서는 to_s를 사용합니다. 문자열로 작업하고 있는지 확인합니다.

이렇게 하면 '정의되지 않은 메서드' 오류를 방지하는 데 도움이 됩니다. 그런 다음 chars 조합 (문자열을 Array로 변환하려면 문자) 및 inject 값을 합산합니다.

블록 내에서 ord를 사용했습니다. 문자를 서수 값으로 변환하는 방법입니다.

마지막으로 모듈로 연산자 %를 사용했습니다. 결과 값이 배열에 맞는지 확인합니다. 이 배열의 각 항목을 '버킷'이라고 합니다.

버킷 배포

이상적으로는 모든 버킷이 고르게 채워지기를 원하므로 값을 검색해야 할 때 최상의 성능을 얻을 수 있습니다.

다음 코드를 사용하여 해시 함수를 테스트할 때 어떤 일이 발생하는지 살펴보겠습니다.

# 모든 요소가 0으로 설정된 BUCKETS 크기의 배열을 생성합니다. table =Array.new(BUCKETS) { 0 }letters =Array('a'..'z')10_000.times do # 임의의 문자열 생성 input =Array.new(5) { letters.sample }.join # 해시 분포 테이블 개수 계산[hash(input)] +=1end

이렇게 하면 다음과 같은 결과가 생성됩니다.

키가 고르게 분포되어 있는 것 같습니다...

...하지만 버킷 수를 늘리면 어떻게 될까요?

이 예에서는 버킷 크기 128(이전에는 32)을 사용했습니다.

[22, 24, 33, 36, 41, 58, 61, 66, 97, 77, 88, 110, 89, 82, 123, 121, 119, 111, 147, 178, 6, 136, 141 180, 190, 193, 185, 192, 223, 209, 208, 196, 215, 251, 233, 226, 231, 236, 219, 218, 227, 6,218, 227, 221,282 182, 165, 188, 141, 160, 135, 130, 117, 139, 106, 121, 85, 70, 93, 74, 61, 57, 54, 5, 40, 46, 32, 2, 3 17, 14, 16, 16, 14, 8, 11, 5, 5, 1, 1, 2, 1, 3, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 0, 4, 3, 6, 0, 2, 9, 13, 11, 12, 14, 12, 23, 12, 22]

더 이상 훌륭한 배포가 아닌 것 같습니다!

무슨 일이야?

문제는 같은 크기의 모든 문자열이 특정 범위에 있기 때문에 해시 함수가 충분하지 않다는 것입니다. 그래서 중간에 빈 버킷이 많이 있습니다.

더 나은 해시 함수

문자열을 인덱스로 변환하는 더 나은 방법이 필요합니다. 한 가지 가능한 구현을 살펴보겠습니다.

BUCKETS =256def 해시(입력) input.to_s.each_char.inject(0) do |sum, ch| (sum <<8) ^ (ch.ord) ^ (sum>> 4) end % BUCKETSend

여기서 일어나는 일은 비트 이동입니다(>> &<< 연산자). 값은 "배타적 OR 연산자"(^ ).

이 비트 이동은 모든 것을 뒤섞어 더 나은 키 배포를 제공합니다. . 완벽하지는 않지만 간단한 ASCII 기반 함수보다 낫습니다 🙂

적절한 해시 함수를 원한다면 MurmurHash와 같은 것을 볼 수 있습니다. Ruby가 사용하는 것이라고 생각합니다.

충돌 처리

아직 유용한 해시 테이블이 없습니다.

왜?

글쎄요, 두 개의 키가 동일한 인덱스로 해시될 때 이전 값을 덮어쓰게 되며 이는 좋지 않다는 것을 눈치채셨을 것입니다!

이것을 해시 충돌이라고 하며 이를 처리하기 위한 몇 가지 전략이 있습니다.

예를 들어 :

• 이중 해싱
• 선형 프로빙
• 별도의 연결

연결 목록을 사용하여 특정 "버킷"에 대한 항목을 저장하는 별도의 연결을 살펴보겠습니다.

따라서 :abc &:ccc 동일한 인덱스로 해시하면 해시 테이블은 다음과 같이 보일 것입니다.

3:[:abc, 100] -> [:ccc, 200]4:nil5:[:yx, 50]

그런 다음 올바른 키를 찾기 위해 선형 검색이 필요합니다.

조회 시간이 O(n) 쪽으로 천천히 저하될 수 있으므로 이는 성능에 영향을 미칩니다. , 예상되는 O(1) 대신 .

이 O(something)에 익숙하지 않다면 "Big-O Notation"이라고 하는 표기법입니다.

연결 목록이 너무 깊어져서 해시 테이블의 성능이 저하되는 것을 방지하려면 더 많은 수의 버킷을 사용하여 해시 테이블을 다시 생성해야 합니다.

Ruby는 자동으로 이 작업을 수행하지만 여전히 알아두면 좋은 정보입니다.

결론

이 기사의 목적은 해시 테이블 구현을 작성하게 하는 것이 아니라 실제로 작동하는 방식을 이해하는 데 도움이 되므로 흥미를 느끼셨기를 바랍니다.

블로그를 계속 운영하려면 이 게시물을 공유하는 것을 잊지 마세요 🙂