2JINISHAPPY 2JINISHAPPY

➕ Hash Table은 java에서의 HashTable API가 아닌 Hash function을 통해 mapping된 value를 저장하는 Table을 뜻함 👇 이전 글 보기 https://2jinishappy.tistory.com/230 빠른 데이터 검색을 위한 Hashing과 Hash Table select * from ~ where key="name" 우리는 종종 위와 같은 쿼리문으로 데이터베이스에 있는 튜플을 조회한다 데이터베이스에 있는 attribute의 key값이 unique하다고 할 때, 테이블의 튜플을 어떻게 조회하는 2jinishappy.tistory.com 서로 다른 key에 대해 hash function으로 변환된 h(x)가 같을 경우, 같은 index에 값을 저장해야 하는 coll..

select * from ~ where key="name" 우리는 종종 위와 같은 쿼리문으로 데이터베이스에 있는 튜플을 조회한다 데이터베이스에 있는 attribute의 key값이 unique하다고 할 때, 테이블의 튜플을 어떻게 조회하는 것이 효과적인지 고민하는 과정에서 해싱의 원리를 찾을 수 있다. 특정 key가 주어졌을 때, 해당 key 값을 가진 record를 찾기 위한 방법으로는 1️⃣ Key를 index로 가진 array로 table 구현 2️⃣ BST 이용 1번은 조회하는 데 O(1)이 소모되는 대신 |max(key)|만큼의 메모리를 요구하기 때문에 실제로 사용하기에는 어렵다. 2번 또한 1번에 비해서는 get, insert의 평균적인 시간이 짧긴 하지만 O(log n)도 수천, 수만개의 re..