Hash ?

hash function

• 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터(message)를 고정된 길이의 데이터(hash value, hash code, digest, hash)로 매핑하는 함수
• 해시함수의 해시값이 최대한 균등하게 나오게 하는것이 중요
• 동일한 input에 대해서 같은 결과를 도출

hashing

• 키(key) : 매핑 전 원래 데이터의 값
• 해시값 (hash value) : 매핑 후 데이터의 값
  -> hashing : 매핑하는 과정 자체

collision

• 해시함수는 해시값의 개수보다 많은 키값을 해시값으로 변환(다대일 대응)하기 때문에 해시함수가 서로 다른 두개의 키에 대해 동일한 해시값을 내는 해시 충돌이 발생
• 충돌을 최소화할 수 있는 해시함수를 사용해야함

Hash Table

• Map 인터페이스를 구현하는 클래스
  • key-value쌍으로 데이터를 저장
  • 키 중복 불가(value는 가능)
    • 동일한 키를 가진 값 추가시, 기존 값이 새 값으로 대체됨
• key와 value에 대해 null 허용X
• 동기화O, thread-safe함, 속도가 느림
  • (멀티스레드 환경이 아니라면) 다른 스레드가 block되고 unblock 되는 대기 시간을 기다려야돼서 상대적으로 느림
• 보조 해시 함수 사용X

Hash Table 해시함수

• 임의의 데이터를 정수로 변환
  • 데이터가 저장되는 곳: 버킷(bucket) 또는 슬롯(slot)
    
    
    
    

Hash Map

• Map 인터페이스를 구현하는 클래스
  • key-value쌍으로 데이터를 저장
  • 키 중복 불가(value는 가능)
    • 동일한 키를 가진 값 추가시, 기존 값이 새 값으로 대체됨
• key 또는 value에 대해 null 허용O
  • 단 하나의 null값을 key로 가질 수 있음, value는 여러 null값 가능
• 동기화X, thread-safe 하지 않음, 속도가 빠름
  • 멀티스레드가 동시에 사용할 때 문제가 발생할 수 잇음
• 보조 해시 함수를 사용해서 해시충돌이 덜 발생 -> 상대적으로 성능이 좋음
• Map의 Key값의 해시코드 변환이 Set의 객체의 해시코드 계산보다 빠름

보조 해시 함수

• key의 해시값을 변형하여 해시 충돌 가능성을 줄임

Hash Set

• Set 인터페이스를 구현하는 클래스
• HashMap 기반으로 저장
  • HashSet의 각 원소(객체)는 HashMap의 key, value는 dummy
• 중복 불가, unique값만 저장
• 단 한개의 null값 허용
• Set의 객체의 해시코드 계산이 Map의 Key값의 해시코드 변환보다 느림

해시 사용예시

• 암호과정 ,
  해시테이블 -> index, 캐싱 , redis

참고

• https://devprofessional.hashnode.dev/7lus66cj7iwyio2uhougioyehoybjo2brcgr7j6q66om6rws7kgwiou5hoq1kck
• https://hello-judy-world.tistory.com/205
• https://yein-lee.tistory.com/41