Hash

- 파이썬의 딕셔너리와 유사

- 데이터를 입력하는 순서 상관 X

- key:value 형식으로 데이터 저장

- value는 중복이 가능하지만 key는 중복 X

- 저장한 데이터 수정 가능

- 모든 데이터 타입으로 접근 가능

- list에 비해 빠른 시간 복잡도 (list=O(N), Hash(Dict)=O(1)) 

- string을 기반으로 데이터를 기록하고 관리해야 할 때 주로 사용 (string 타입의 key)

 

해쉬 함수(Hash Function)

- 임의의 길이를 갖는 임의의 데이터(key)를 고정된 길이의 데이터(해시 값)로 매핑하는 함수

- hash() = 해쉬값 설정 (해쉬값은 랜덤으로 부여됨, 중복 가능성 존재 - 중복 발생 = 해쉬 충돌 발생)

※ Java의 경우에는 hashCode() 

 

※ 만약 중복되는 데이터(ex: 동명이인)가 있어 해당 데이터를 key로 사용하지 못하는 경우 그 데이터를 key가 아닌 value로 지정한 뒤 hash(value):value 형태로 딕셔너리에 데이터를 저장하면 편리함

 

해쉬 충돌 해결 방법

- 해쉬 충돌(hash collision) = 서로 다른 key인데 해쉬값이 같아 같은 value를 가지는 경우 (발생 경우가 희박함)

 

1. 체이닝(Chaining)

- 같은 해쉬값을 갖는 원소들을 하나의 연결 리스트에 모아 관리

- 리스트가 길어질수록 처리 시간이 늘어나 빠른 시간 복잡도라는 해쉬의 장점이 무의미해짐

 

2. 개방 주소 방법(Open Addressing)

 ① 선형 조사

   - 충돌이 일어난 바로 뒷 자리에 값을 입력

    (만약 바로 뒷 자리에도 값이 이미 있으면 그 다음 뒷뒷자리로 넘어감, 빈 공간을 찾을때까지 반복) 

   - 계산이 단순하지만 데이터들이 특정 영역에 몰릴 수 있고 시간이 많이 소요됨

 

 ② 이차원 조사

    - 

 

 ③ 더블 해싱

    -