해시 테이블은 연관 방식으로 데이터를 저장하는 데이터 구조입니다. 해시 테이블에서 데이터는 각 데이터 값에 고유한 인덱스 값이 있는 배열 형식으로 저장됩니다. 원하는 데이터의 인덱스를 알면 데이터에 대한 액세스가 매우 빨라집니다.
따라서 데이터의 크기에 관계없이 삽입 및 검색 작업이 매우 빠른 데이터 구조가 됩니다. 해시 테이블은 배열을 저장 매체로 사용하고 해시 기법을 사용하여 요소가 삽입되거나 위치할 인덱스를 생성합니다.
해싱
해싱은 키 값의 범위를 배열의 인덱스 범위로 변환하는 기술입니다. 모듈로 연산자를 사용하여 키 값 범위를 얻을 것입니다. 크기가 20인 해시 테이블의 예를 고려하고 다음 항목이 저장됩니다. 항목은 (키, 값) 형식입니다.
여기에 키를 입력하고 테이블에 대한 인덱스를 생성하는 해시 함수가 있습니다. 이 인덱스는 값이 저장된 위치를 알려줍니다. 이제 키와 관련된 값을 검색할 때마다 키에 대해 해시 함수를 다시 실행하고 거의 일정한 시간에 값을 가져오기만 하면 됩니다.
해시 함수는 디자인하기가 꽤 어렵습니다. 예를 들어 보겠습니다 -
다음 해시 함수가 있다고 가정해 보겠습니다.
예시
function modBy11(key) {
return key % 11;
} 그리고 저장하려는 키-값 쌍에 대해 이것을 실행하기 시작합니다. 예를 들어 -
- (15, 20) - 해시 코드:4
- (25, 39) - 해시 코드:3
- (8, 55) - 해시 코드:8
- (26, 84) - 해시 코드:4
여기에서 충돌이 있음을 알 수 있습니다. 즉, 먼저 15를 저장한 다음 이 해시 함수로 키 26을 만나면 동일한 구멍에서 이 항목을 수정하려고 합니다. 이것을 충돌이라고 합니다. 그리고 이러한 상황을 처리하려면 충돌 처리 메커니즘을 정의해야 합니다. 잘 정의된 간단한 충돌 해결 알고리즘이 있습니다. 예를 들어 -
- 선형 탐색:이 알고리즘에서는 빈 셀을 찾을 때까지 다음 셀을 조사하여 배열의 다음 빈 위치를 검색할 수 있습니다. 이 예에서는 4의 구멍을 가져왔으므로 5를 채울 수 있습니다.
- Separate Chaining:이 구현에서는 해시 테이블의 각 위치를 목록과 연결합니다. 충돌이 발생할 때마다 이 목록의 끝에 키-값 쌍을 추가합니다. 체인이 계속 길어지면 검색 시간이 훨씬 길어질 수 있습니다.
이제 해시 테이블이 작동하는 방식과 충돌 해결 방법을 이해했으므로 HashTable 클래스를 구현해 보겠습니다.
구현할 방법
구현 시 이러한 방법을 구현할 것입니다. −
- put(key, value):새로운 키-값 쌍을 해시 테이블에 추가
- get(key):키와 관련된 값을 가져옵니다.
- remove(key):테이블에서 키-값 쌍을 제거합니다.
- forEach():모든 키-값 쌍에 대한 반복 허용
- static join():2개의 해시 테이블을 새 테이블에 결합하는 정적 메소드