저장할 키값을 해시함수를 이용해 해시값으로 변환해 해시테이블의 버킷에 저장
해시를 사용하지 않은 경우:
→ 키값이 오름차순으로 정렬된 배열에서 이진 검색법으로 조사하여 검색/삽입/삭제 O(n)
해시를 사용한 경우:
→ 키값을 해시값으로 변환한 인덱스에 저장하므로 검색/삽입/삭제시 O(1)
: 새로운 값을 추가할 때 추가할 값의 해시값에 해당하는 곳이 이미 채워진 경우(해시값이 중복되는 경우)
→ 버킷의 값은 첫 번째 노드의 참조, 빈 버킷의 값은 null
장점: 미리 공간을 많이 잡아 놓을 필요 없음
단점: 연결리스트가 길어질 경우 비효율적임