데일리디벨롭

collision 이전 포스트에서 알아본 Hash table에서 발생한 collision을 해결하는 방법에는 대표적으로 2가지 방법이 있다. open addressing 방식은 collision이 발생하면 미리 정한 규칙에 따라 hash table이 비어있는 slot을 찾는다. 빈 slot을 찾는 방법에 따라 Linear Probing, Quadreatic Probing, Double Hashing으로 나뉘게 된다. separete chaining방식은 linked list를 이용한다. 만약 collision이 발생하면 linked list에 노드(slot)를 추가하여 데이터를 저장한다. Open addressing Open addressing방식은 collision이 발생하면 미리 정한 규칙에 따라 h..

Hash table hash table은 효율적인 탐색(빠른 탐색)을 위한 자료구조로써, key-value쌍의 데이터를 입력받는다. hash function h에 key값을 입력으로 넣어 얻은 해시값 h(k)를 위치로 지정하여 key-value 데이터 쌍을 저장한다. Direct-address Table hash table을 알아보기에 앞서, Direct-address Table을 알아보자. Direct-address Table(직접 주소화 테이블)이란, key값으로 k를 갖는 원소는 index k에 저장하는 방식이다. 즉, 아래 데이터를 기준으로 key값을 index로 설정하여 index 3번에는 맹짱구를 저장하고, 5번에는 김철수, 6번 정훈이, 7번에는 남맹구를 저장한다. key: 출석번호, val..