컴퓨팅에서해시테이블[해시맵)은키(고유한문자열이나정수)를기반으로개체에사실상직접적인액세스를제공하는데이터구조를말합니다。해시테이블은해시함수를사용해인덱스를버킷이나슬롯어레이로연산하는데,여기에서원하는값을찾을수있습니다。여기에사용되는키의주된특징을소개합니다。
- 사용되는키는ssn，전화번호계좌번호등무엇이든가능
- 반드시고유한키가있어야함
- 각각의키가값과연결됨(즉값에매핑됨)
해시버킷은정렬이나검색용도로데이터항목을배분하는데쓰입니다。이작업의목표는서로연결된목록을약화하여특정항목의검색결과에짧은기간내에액세스할수있게하는것입니다。
버킷을사용하는해시테이블은사실상어레이하나와연결된목록하나의조합이라고할수있습니다。어레이의각소[해시테이블]이연결된목록의헤더가됩니다。같은위치로해시되는모든소가해당목록에저장됩니다。해시함수가각각의레코드를버킷중하나에속한첫슬롯에할당합니다。슬롯에이미자리가찬경우，버킷슬롯을차례로검색하여열린슬롯을찾아냅니다。버킷이완전히꽉찬경우,해당레코드는테이블끝에있는무한용량오버플로버킷에저장됩니다。모든버킷이같은오버플로버킷을공유합니다。다만잘된구현이라면레코드를여러버킷에골고루분배하는해시함수를써서오버플로버킷에들어가는레코드를가능한한적게합니다。