[ Data Structures ]Hash, Hash Table

What is Hash? (해시란 무엇인가 ) 

key : value 를 갖는 데이터를 관리하고 유지하는 자료구조 (Data Structure) 중 하나이다.  

 

해시는 배열과 달리 String 타입이나 다른 어떤 데이터형을 기반으로 자료구조를 접근하고 데이터를 관리할 수 있게 해준다. 

특히, String을 기반으로 정보를 기록하고 관리해야 할 때 (단순 배열 사용 X) 

 

Hash Function : 키 값을 수치( > 0 )로 변환하는 함수 

: the method/function performing the conversion is referred to as "hash function" 

h(x) = x mod N ( for integer keys )

 

Hash Table : 자료를 해시함수의 결과를 사용해 위치(index)의 버켓에 배치하는 방법 

: To speed up searching for an entry, we can create an array of holders/buckets of these entries.

: The resulting data structure is hence a table.

 

 

 

* Hash의 장점

(1) 모든 데이터 타입으로 접근이 가능

 

(2) 빠른 데이터 접근 속도 => 접근 속도(insert, search ,delete)  : O(1)

 

(3) 얼마나 많은 키가 삽입되거나 삭제되는지 또 얼마나 자주 이런 과정이 일어날 지 알수 없을때 사용

 

 

* Hash의 단점(Drawbacks)

(1) 공간의 낭비( Wastage of Space ) - Some Parts of hash table are never used, ans uses extra space for links.

= If N is much larger than the actual number of stored elements, then a lot of space is wasted 

 

(2) If the chain becomes long, then search time can become O(n) in worst case.

 

(3) 이미 인덱스 버켓에 자리가 차있을때 충돌(Collision)이 발생  ( 충돌 - 서로 다른 키의 해시 연산의 결과가 같을 때) 

==> 충돌을 대처하는 방법 

1) Separate Chanining : each bucket a[i] stores a small map(list)

 

2) Open Addressing 

: store the entries directly in the bucket ( one entry per bucket) 

공간은 절약해주지만, 충돌을 다루는데 더 복잡해질 수 있다. 

* 각 bucket 하나는 무조건 1개의 key만 저장한다. 

( it requires that the load factor is always at most 1 and that the entries are strored directly into the cells of the bucket array itself. 

 

- Linear Proving : 이미 만든 버켓을 소모하기 위한 방법

A[i +1 mod N] i = h(x) if a[i+1] occupied, try A[i+2] mod N 

 

 

- Quadratic Proving 

A[i+f(j) mod N] f(j) = j^2 ( 1,4,9,16,...) 

 

- Double Hashing 

A[i+f(j) mod N] f(j)=j.h'(k) j=1,2,3...

 

 

6) Resizing : 버켓이 다 차면, 테이블의 크기를 늘려준 다음, linear proving을 사용 

 

 

 

 

 

* methods of Hash : get / put / getOrDefault 

 

[HashMap에 값을 집어넣는 것]

put : Hash Map 안에 key와 value를 넣을 수 있음 

 

[HashMap에서 값을 가져오는 것] 

get 

=> hashMap.get("A") : "A"라는 Key가 존재한다고 가정 -> But, A라는 Key가 존재하지 않으면 ERROR!

 

getOrDefault 

=> 매번 Key가 존재하는 지 확인하고 get을 사용해야하는 번거로움을 개선한 함수 

getOrDefault ("A", false) : A가 있다면, A의 Value를 반환. Otherwise, print false!  

 

 

 

(ex) Programmers  - 완주하지 못한 선수

https://coding-grandpa.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%99%84%EC%A3%BC%ED%95%98%EC%A7%80-%EB%AA%BB%ED%95%9C-%EC%84%A0%EC%88%98-%ED%95%B4%EC%8B%9C-Lv-1

 

 

참고 사이트 : https://www.javatpoint.com/hash-table