데이터 구조의 해시 테이블: Python 예시
사라 첸
해싱이란 무엇입니까?
해시는 고정된 길이를 갖는 값이며 수학 공식을 사용하여 생성됩니다. 해시 값은 데이터 압축, 암호화 등에 사용됩니다. 데이터 인덱싱에서는 해시 값을 생성하는 데 사용된 값에 관계없이 고정된 길이 크기를 갖기 때문에 사용됩니다. 다양한 길이의 다른 값에 비해 해시 값이 최소한의 공간을 차지하도록 만듭니다.
해시 함수는 수학적 알고리즘을 사용하여 키를 해시로 변환합니다. 해시 함수가 둘 이상의 키에 대해 동일한 해시 값을 생성하면 충돌이 발생합니다.
해시 테이블이란 무엇입니까?
A 해시 테이블 키와 값의 쌍을 사용하여 값을 저장하는 데이터 구조입니다. 각 값에는 해시 함수를 사용하여 생성된 고유 키가 할당됩니다.
키의 이름은 연관된 값에 액세스하는 데 사용됩니다. 이를 통해 해시 테이블의 항목 수와 관계없이 해시 테이블에서 값을 매우 빠르게 검색할 수 있습니다.
해시 함수
예를 들어 직원 기록을 저장하려는 경우 각 직원은 직원 번호를 사용하여 고유하게 식별됩니다.
직원 번호를 키로 사용하고 직원 데이터를 값으로 할당할 수 있습니다.
위의 접근 방식에는 다음 순서의 추가 여유 공간이 필요합니다. (m * n2) 여기서 변수 m은 정렬, 변수 n은 사원번호의 자릿수이다. 이 접근 방식은 저장 공간 문제를 야기합니다.
해시 함수는 직원 번호를 가져와 이를 사용하여 해시 정수 값, 고정 숫자를 생성하고 저장 공간을 최적화함으로써 위의 문제를 해결합니다. 해시 함수의 목적은 저장하려는 값을 참조하는 데 사용할 키를 생성하는 것입니다. 이 함수는 저장할 값을 승인한 다음 알고리즘을 사용하여 키 값을 계산합니다.
다음은 간단한 해시 함수의 예입니다.
h(k) = k1 % m
이리,
- h(k)는 매개변수 k를 받는 해시 함수입니다. 매개변수 k는 키를 계산하려는 값입니다.
- k1 % m은 해시 함수의 알고리즘이며, k1은 저장하고자 하는 값이고, m은 리스트의 크기입니다. 모듈러스 연산자를 사용하여 키를 계산합니다.
예시
크기가 3이고 다음 값을 갖는 목록이 있다고 가정해 보겠습니다.
[1,2,3]
위 공식을 사용하여 각 값이 차지해야 하는 위치를 계산할 수 있습니다.
다음 이미지는 해시 테이블에서 사용 가능한 인덱스를 보여줍니다.
단계 1) 다음과 같이 첫 번째 값이 차지할 위치를 계산합니다.
h(1) = 1% 3
= 1
가치 1개가 차지할 것이다 공간 색인 1
단계 2) 두 번째 값이 차지할 위치를 계산합니다.
h(2) = 2% 3
= 2
가치 2개가 차지할 것이다 공간 색인 2
단계 3) 세 번째 값이 차지할 위치를 계산합니다.
h(3) = 3% 3
= 0
가치 3개가 차지할 것이다 공간 색인 0
최종 결과
이제 채워진 해시 테이블은 다음과 같습니다.
좋은 해시 함수의 특성
좋은 해시 함수는 다음과 같은 특성을 가져야 합니다.
- 해시를 생성하는 공식은 알고리즘에 저장될 데이터 값을 사용해야 합니다.
- 해시 함수는 동일한 양의 입력 데이터에 대해서도 고유한 해시 값을 생성해야 합니다.
- 이 기능은 충돌 횟수를 최소화해야 합니다. 둘 이상의 값에 대해 동일한 값이 생성되면 충돌이 발생합니다.
- 값은 가능한 전체 해시에 일관되게 배포되어야 합니다.
충돌
충돌은 알고리즘이 둘 이상의 값에 대해 동일한 해시를 생성할 때 발생합니다.
예를 봅시다.
다음과 같은 값 목록이 있다고 가정해 보겠습니다.
[3,2,9,11,7]
해시 테이블의 크기가 7이라고 가정하고 다음 공식을 사용합니다(k1 % m) 여기서 m은 해시 테이블의 크기입니다.
다음 표는 생성될 해시 값을 보여줍니다.
| 키 | 해시 알고리즘(k1%m) | 해시 값 |
|---|---|---|
| 3 | 3 % 7 | 3 |
| 2 | 3 % 7 | 2 |
| 9 | 3 % 7 | 2 |
| 11 | 3 % 7 | 4 |
| 7 | 3 % 7 | 0 |
위 결과에서 볼 수 있듯이 2와 9의 값은 동일한 해시값을 가지며, 각 위치에 XNUMX개 이상의 값을 저장할 수 없습니다.
주어진 문제는 체이닝이나 프로빙을 사용하여 해결할 수 있습니다. 다음 섹션에서는 체이닝과 프로빙을 자세히 설명합니다.
쇠사슬
체이닝(Chaining)은 각각 고유한 인덱스를 가지고 있는 연결 리스트를 이용하여 충돌 문제를 해결하는 기술이다.
다음 이미지는 체인 목록이 어떻게 보이는지 시각화합니다.
2와 9는 모두 같은 인덱스를 차지하지만 연결리스트로 저장됩니다. 각 목록에는 고유한 식별자가 있습니다.
연결 목록의 이점
체인 리스트의 이점은 다음과 같습니다.
- 연결된 목록은 삽입 순서가 O(1)이므로 데이터를 삽입할 때 성능이 더 좋습니다.
- 연결된 목록을 사용하는 해시 테이블의 크기를 조정할 필요는 없습니다.
- 여유 공간이 있으면 많은 수의 값을 쉽게 수용할 수 있습니다.
프로빙
충돌을 해결하는 데 사용되는 또 다른 기술은 프로빙(probing)입니다. 프로빙 방법을 사용할 때 충돌이 발생하면 간단히 이동하여 값을 저장할 빈 슬롯을 찾을 수 있습니다.
조사 방법은 다음과 같습니다.
| 방법 | 상품 설명 |
|---|---|
| 선형 프로빙 | 이름에서 알 수 있듯이 이 방법은 충돌이 발생한 위치에서 시작하여 앞으로 이동하면서 선형적으로 빈 슬롯을 검색합니다. 목록 끝에 도달했는데 빈 슬롯이 발견되지 않은 경우. 검색은 목록의 시작 부분에서 시작됩니다. |
| XNUMX 차 프로빙 | 이 방법은 XNUMX차 다항식을 사용하여 다음으로 사용 가능한 여유 슬롯을 찾습니다. |
| Double 해싱 | 이 기술은 보조 해시 함수 알고리즘을 사용하여 사용 가능한 다음 여유 슬롯을 찾습니다. |
위의 예를 사용하면 프로빙을 사용한 후의 해시 테이블은 다음과 같이 나타납니다.
해시 테이블 작업
여기에는 Opera해시 테이블에서 지원되는 기능:
- 삽입 -이 Opera해시 테이블에 요소를 추가하는 데 사용됩니다.
- 수색 -이 Opera키를 사용하여 해시 테이블의 요소를 검색하는 데 사용됩니다.
- 삭제 -이 Opera해시 테이블에서 요소를 삭제하는 데 사용됩니다.
데이터 삽입 작업
삽입 연산은 해시 테이블에 값을 저장하는 데 사용됩니다. 해시 테이블에 새 값이 저장되면 인덱스 번호가 지정됩니다. 인덱스 번호는 해시 함수를 사용하여 계산됩니다. 해시 함수는 인덱스 번호를 계산할 때 발생하는 모든 충돌을 해결합니다.
데이터 작업 검색
검색 연산은 인덱스 번호를 사용하여 해시 테이블에서 값을 조회하는 데 사용됩니다. 검색 연산은 검색 인덱스 번호에 연결된 값을 반환합니다. 예를 들어, 인덱스 6에 값 2을 저장하면 인덱스 번호 2를 사용한 검색 연산은 값 6을 반환합니다.
데이터 삭제 작업
삭제 작업은 해시 테이블에서 값을 제거하는 데 사용됩니다. 삭제하려면 Opera삽입은 인덱스 번호를 사용하여 수행됩니다. 값이 삭제되면 인덱스 번호는 해제됩니다. 삽입 작업을 사용하여 다른 값을 저장하는 데 사용할 수 있습니다.
해시 테이블 구현 Python 예시
키의 해시 값을 계산하는 간단한 예를 살펴보겠습니다.
def hash_key( key, m):
return key % m
m = 7
print(f'The hash value for 3 is {hash_key(3,m)}')
print(f'The hash value for 2 is {hash_key(2,m)}')
print(f'The hash value for 9 is {hash_key(9,m)}')
print(f'The hash value for 11 is {hash_key(11,m)}')
print(f'The hash value for 7 is {hash_key(7,m)}')
해시 테이블 코드 설명
이리,
- 매개변수 key와 m을 받아들이는 함수 hash_key를 정의합니다.
- 해시 값을 결정하기 위해 간단한 모듈러스 연산을 사용합니다.
- 값 7로 초기화되는 변수 m을 정의합니다. 이것은 해시 테이블의 크기입니다.
- 3의 해시 값을 계산하고 인쇄합니다.
- 2의 해시 값을 계산하고 인쇄합니다.
- 9의 해시 값을 계산하고 인쇄합니다.
- 11의 해시 값을 계산하고 인쇄합니다.
- 7의 해시 값을 계산하고 인쇄합니다.
위 코드를 실행하면 다음과 같은 결과가 생성됩니다.
The hash value for 3 is 3 The hash value for 2 is 2 The hash value for 9 is 2 The hash value for 11 is 4 The hash value for 7 is 0
Python 사전 예
Python Dictionary라는 내장 데이터 유형이 함께 제공됩니다. 사전은 해시 테이블의 예입니다. 키와 값 쌍을 사용하여 값을 저장합니다. 해시 값은 자동으로 생성되며 모든 충돌은 백그라운드에서 해결됩니다.
다음 예제에서는 사전 데이터 형식을 사용하는 방법을 보여줍니다. 파이썬 3
employee = {
'name': 'John Doe',
'age': 36,
'position': 'Business Manager.'
}
print (f"The name of the employee is {employee['name']}")
employee['position'] = 'Software Engineer'
print (f"The position of {employee['name']} is {employee['position']}")
employee.clear()
print (employee)
이리,
- 사전 변수 직원을 정의합니다. 키 이름은 John Doe 값을 저장하는 데 사용되며 age는 36을 저장하고 위치는 Business Manager 값을 저장합니다.
- 키 이름 값을 검색하여 터미널에 인쇄합니다.
- 키 위치 값을 소프트웨어 엔지니어 값으로 업데이트합니다.
- 키 이름과 위치의 값을 인쇄합니다.
- 사전 변수 직원에 저장된 모든 값을 삭제합니다.
- 직원의 값을 인쇄합니다.
위 코드를 실행하면 다음과 같은 결과가 생성됩니다.
The name of the employee is John Doe.
The position of John Doe is a Software Engineer.
{}
복잡성 분석
해시 테이블은 최상의 시나리오에서 평균 시간 복잡도가 O(1)입니다. 최악의 시간 복잡도는 O(n)입니다. 최악의 시나리오는 많은 값이 동일한 해시 키를 생성할 때 발생하며, 프로빙을 통해 충돌을 해결해야 합니다.
실제 애플리케이션
실제로 해시 테이블은 데이터를 저장하는 데 사용됩니다.
- 데이터베이스
- 연관 배열
- 설정
- 메모리 캐시
해시 테이블의 장점
해시 테이블 사용의 장점/이점은 다음과 같습니다.
- 해시 테이블은 데이터 조회, 기존 값 삽입, 삭제 시 성능이 뛰어납니다.
- 해시 테이블의 시간 복잡도는 테이블에 있는 항목 수에 관계없이 일정합니다.
- 대규모 데이터 세트로 작업할 때에도 매우 잘 수행됩니다.
해시 테이블의 단점
해시 테이블 사용의 단점은 다음과 같습니다.
- null 값을 키로 사용할 수 없습니다.
- 를 사용하여 키를 생성할 때 충돌을 피할 수 없습니다. 해시 함수. 이미 사용 중인 키가 생성되면 충돌이 발생합니다.
- 해싱 함수에 충돌이 많으면 성능이 저하될 수 있습니다.
요약
- 해시 테이블은 한 쌍의 키와 값을 사용하여 데이터를 저장하는 데 사용됩니다.
- 해시 함수는 수학적 알고리즘을 사용하여 해시 값을 계산합니다.
- 둘 이상의 값에 대해 동일한 해시 값이 생성되면 충돌이 발생합니다.
- 연결은 연결된 목록을 생성하여 충돌을 해결합니다.
- 프로빙은 해시 테이블에서 빈 슬롯을 찾아 충돌을 해결합니다.
- 선형 프로빙은 충돌이 발생한 슬롯부터 시작하는 값을 저장하기 위해 다음 빈 슬롯을 검색합니다.
- XNUMX차 프로빙은 충돌이 발생할 때 다항식을 사용하여 다음 여유 슬롯을 찾습니다.
- Double 해싱은 충돌이 발생할 때 보조 해시 함수 알고리즘을 사용하여 다음 여유 슬롯을 찾습니다.
- 해시 테이블은 다른 데이터 구조에 비해 성능이 더 좋습니다.
- 해시 테이블의 평균 시간 복잡도는 O(1)입니다.
- Python의 사전 데이터 유형은 해시 테이블의 예입니다.
- 해시 테이블은 삽입, 검색, 삭제 작업을 지원합니다.
- null 값은 인덱스 값으로 사용할 수 없습니다.
- 해시 함수에서는 충돌을 피할 수 없습니다. 좋은 해시 함수는 발생하는 충돌 횟수를 최소화하여 성능을 향상시킵니다.
