HASH TABLE 이란?

 hash map 과 map 의 차이점은 hash map 은 내부적으로 hash table 을 사용하고 map 은 red-black tree 를 사용한다고 한다. 

그렇다면 Hash Table 이란? 

해쉬 테이블 : key , value 로 데이터를 저장하는 자료구조 -> key 가 있으니 빠르게 조회가 가능하다. 

각각의 key 값에 해시함수적용. index 생성, -> 이 값을 활용해 값을 저장하거나 검색. 

실제 값 저장 : 버킷 또는 슬롯 에 저장. 

그렇다면 hash function 은 무엇일까? : 임의의 길의의 데이터를 고정된 길이의 데이터로 매핑하는 함수. 

해시함수는 임의의 길이의 데이터를 입력받아 -> 일정한 길이의 비트열로 반환시켜주는 함수 

출력값은 고정된 길이 

동일한 값이 입력 -> 동일한 출력값을 보장 

여기서 역상저항성 : 입력값 a -> 입력값 b 출력 

입력값 b 로는 입력값 a 를 알 수 없다. (계산못함)

제2역상저항성 : 입력값 a와 출력값 b 를 모두 알고 있을때 똑같은 값을 반환하는 b 를 찾는 또다른 값을 만드는것 불가능. 

 -> 단방향 암호화 : a로 만들어진 b를 가지고 다시 a로 역산할 수 없다. 

그러면 다시 돌아가서 해시테이블은 (key , value ) 에서 각각의 key 값에 해시함수를 적용항 -> 배열의 고유한 index 를 생성하고 이 index 를 활용하여 값을 저장하거나 검색. 

key 값으로 데이터를 찾을때 해시 함수를 1번만 수행. -> 매우 빠르게 데이터를 저장 삭제 조회 

해시테이블의 평균 시간복잡도는 o(1)