hash

[자료구조] 해시테이블

1. 해시 테이블이란? 우리가 누군가에게 연락하기 위해서는 핸드폰 번호를 입력해서 할 수 있겠지만 이런 경우 그 사람의 연락처가 무엇인지 기억하기 위한 노력이 필요합니다. 그런데 만약 100명, 아니 10,000명의 사람의 연락처를 기억하고 그것을 바로 생각해서 연락하는 것은 음, 쉽지 않겠죠? 그래서 그것을 기억하기 쉽게 단축 번호(1, 2, ..., N)를 등록하거나 이름, 별명 등 다양한 방식으로 그 전화번호를 저장하는게 보통입니다. 여기서 홍길동이라는 사람의 연락처를 찾는다고 하고, ㄱ~ㅎ까지 순차적으로 확인한다고 하면 등록된 연락처의 수에 비례해서 찾는 시간이 걸립니다. 또한 탐색에서 빠르다고 하는 이진 탐색을 이용해도, 탐색하는 양을 절반씩 줄여나가 많이 개선됩니다. 하지만 결국에는 데이터의 ..