[CLRS] [11-1] Direct-address tables

0. Intro

- CLRS 11챕터에서부턴 Hash Table에 대해서 알아가게 될 것이다.

- 우선 본격적으로 알아가기전에 Direct-address tables에 대해서 알아보자.

 

1. Direct-address tables?

- Direct-Address table은 해시 테이블의 한 종류로, 특정한 키 값을 사용하여 데이터를 직접적으로 저장하는 구조이다.

- 즉, 데이터의 키를 직접 인덱스로 사용하여 데이터를 저장하거나 검색한다.

 

2. method

2.1. Insert(삽입)

def insert(table, k, value):
	table[k] = value

 

2.2. Search(검색)

def search(table,k):
	return table[k]

 

2.3. Delete(삭제)

def delete(table,k):
	table[k] = None

 

3. 장/단점

3.1. 장점

i) O(1)의 시간복잡도로 삽입, 삭제, 검색이 가능하므로 매우 빠르다.

ii) 구조가 간단하고 구현이 쉽다.

 

3.2. 단점

i) 키 값의 범위가 크면 배열의 크기가 커져서 메모리 낭비가 발생할 수 있다.

- 예를 들어, 키의 최솟값이 0이고 최댓값이 1,000,000이라면, 1,000,001개의 공간이 필요하다.

 

ii) 스파스 데이터(Sparse Data)

- 사용되지 않는 키 값이 많을 수록, 많은 메모리를 낭비하게 된다.