해시 → 데이터를 어떠한 수로 나눈 값을 인덱스로 사용하여 저장
예를 들어, 메인 메모리의 주소가 100만까지 있으면 특정 데이터룰 100만으로 나누어 나머지 값을 주소값으로 저장.
하지만, 나눈 값이 서로 같을수도 있음
해시값이 같은 데이터를 저장하기 위해 나중에 들어온 값을 연결 리스트로 저장한다
값을 찾을 때는 연결 리스트를 순회하며 끝을 만났을 때는 값이 없다고 판단한다
값을 저장할 때 해시로 얻은 주소에 이미 값이 있다면 그 다음 자리에 값이 비어있는지 찾는다. 그 자리에도 값이 있다면 없는 주소를 얻을 때까지 반복한다.
이 때, 데이터들이 한쪽에만 몰리는 클러스터가 생길 수 있다
데이터를 찾을 때는 원하는 값을 찾거나, None을 찾을 때 까지 이동한다.
데이터를 삭제할 때는 주의가 매우 필요하다. 무턱대고 지우다가는 데이터 본인의 뒤의 다른 데이터가 밀려난 데이터를 경우 본인의 자리에서 None을 반환하여 값이 없다고 인식할 수도 있기 때문이다.
tombsotme (묘비) 세우기
삭제된 자리에 묘비를 세워 이 자리는 비어있는 자리가 아닌 무언가가 삭제된 자리라고 인식하게 한다. 이로 하여금 뒤의 데이터가 중간에 None을 만나 검색이 힘들게 하는 상황을 방지한다