해시 테이블

키(이름표)로 값을 빠르게 찾아주는 자료구조다. 키를 숫자로 뭉개는 계산(해시 함수)을 거쳐 그 숫자가 가리키는 칸에 값을 넣어두면, 나중에 같은 키로 같은 칸을 바로 찾아가 값을 꺼낸다. 목록을 처음부터 끝까지 뒤지지 않아도 돼서 찾는 속도가 거의 O(1)이다. 자바의 HashMap이 이 구조로 만들어져 있다.