[Algorithm] 자료구조 - 해시 테이블 (Hash table)

 

해시 테이블 (Hash table)

---

키(key)에 값(value)을 매핑하는 자료 구조

- 해시 테이블의 각 위치는 슬롯(slot)이라고 한다

- 해시 함수(hash function)로 배열의 인덱스를 계산한다

- 실제 저장된 키의 개수가 가능한 키의 개수보다 적을 때 해시 테이블을 사용

- 해시 테이블은 배열의 개념을 일반화한다

- 딕셔너리를 구현하는 데 유용한 자료 구조

 

 

 

해시 함수로 데이터를 저장하는 과정

---

1. 데이터를 저장할 크기 M인 배열을 생성, 이 배열을 해시 테이블이라 한다

2. 해시 함수로 키의 해시 코드를 찾는다

3. 해시 코드를 해시 테이블의 크기로 나눈 나머지를 구해 데이터를 저장할 인덱스로 사용

4. 데이터를 지정된 인덱스에 저장

 

 

 

해시 테이블에서 해시 함수로 데이터를 찾는 과정

---

1. 해시 함수로 검색 중인 키의 해시 코드를 찾는다

2. 해시 코드를 해시 테이블의 크기로 나눈 나머지를 구해 저장된 데이터의 인덱스를 구한다

3. 지정된 인덱스에서 값을 검색

 

 

 

해시 테이블의 API와 시간 복잡도

API (Application Programming Interface)

---

- Insert(x) : x를 데이터 세트에 추가

- Delete(x) : 데이터 세트에서 x를 삭제

- Search(x) : 데이터 세트에서 x를 검색

> 해시 테이블에서 원소를 찾는 데 걸리는 평균 시간은 O(1) : 검색 성능이 뛰어남

 

 

 

 

💡 자료 구조 : codesyun.tistory.com/106

[Algorithm] 자료 구조(Data Structure) 란?