해시 테이블: 수학 함수를 사용해 데이터의 위치를 알려준다. 특히 정보를 탐색해서 빠르게 읽고 싶은 순수한 저장 요도의 경우에 해시 테이블이 유용하다.

배열은 개별 데이터 조각을 저장하는 간결한 구조와 효율적인 탐색 메커니즘을 제공하지만, 해당 원소의 인덱스를 알 때만 효율적이다.

인덱스가 있으면 상수 시간에 원하는 원소를 조회할 수 있다.

해시 테이블은 수학 함수를 사용해 값의 인덱스를 계산하기 때문에 값을 바로 배열의 상자로 매핑할 수 있다. 단점은 모든 매핑이 완벽하지만은 않다는 것이다. 서로 다른 값이 같은 위치로 매핑되는 해시 충돌이 발생할 수 있다.

10.1 키를 사용한 저장과 탐색

정수 값의 효율적인 탐색을 위한 이상적인 인덱싱 방법 : 바로 있을 수 있는 모든 값에 대해 개별적으로 배열 상자를 유지하고, 값을 사용해 그 상자를 인덱싱하는 것.

동적으로 크기가 조정되는 데이터를 저장하기 위해 포인터 배열을 사용하는 방법

CoffeeRecord {
	String: Name
	String: Brad
	Integer: Rating
	FloatingPoint: Cost_Per_Pound
	Boolean: Is_Dark_Roast
	String: Other_Notes
	Image: Barcode
}

키(key) : 데이터와 함께 저장되거나 데이터로부터 유도된 단일 값이며, 레코드를 식별할 때 키를 쓸 수 있다.

키에서는 색인을 생성하는 함수가 필요하다.

10.2 해시 테이블

해시 테이블은 수학적인 매핑을 사용해 키 공간을 압축한다. 해시 테이블은 원래의 키를 테이블 상 위치(해시 값)로 매핑하는 해시 함수를 사용해 큰 키 공간을 작은 영역으로 축소시킨다.

해시 함수는 정수가 아닌 값들을 정수 범위로 매핑할 수 있기 때문에 키가 정수가 아닐 떄 생기는 문제를 해결할 수 있다.