Hash 해시
긁어 모음
충돌이 일어나지 않는다면, 검색, 추가, 삭제가 대부분 완성되므로, 시간 복잡도가
Hash Function 해시 함수
perfect hash function : key -> slot 로 1:1 구조로 데이터를 넣기 때문에 아주 좋지만,,, ideal(비현실적인)한 방법이다..
universal hash function :
무조건 collision이 생기지만 그 크기가 반비례한다면
해시법 : 데이터를 저장할 위치 (인덱스) 를 간단한 연산으로 구하는 방법
기존의 리스트를 해시값을 인덱스로 저장한 새로운 배열을 해시 테이블이라고 한다
해시값 : 데이터에 접근할 때 기준이 되는 값
key 가 int 형인 경우에는 %capacity 값을 해시값으로
아닐 경우에는 sha256알고리즘, encode, hexdigest, int() 표준 라이브러리로 타입 변환 하여 사용
Capacity : 해시 테이블의 크기를 지정
충돌이 생겼을 때 ( collision )
체인법 : linked list로 같은 인덱스 안에 추가 - 추가
node 클래스를 생성해서 key, value, next:node (다음노드 참조)
오픈 주소 법 : 충돌이 일어나면, 재해시(re-hashing)통해 빈 버킷을 찾는다
좋은 해시 함수
→ less collision (충돌 적은)
→ fast compution (계산 빠른): 이 두 특성이 균형을 이루는게 좋은 거지
휴리스틱
곱셈, 나눗셈 이용한 해싱함수
나눗셈 h(k) = k mod m
곱하기 h(k) = [ m(kA mod 1) ] 내림연산 floor?
유니버설 해싱 O(n)
랜덤화된 방법 사용해 좋은 성능을 증명
악의적인 사용자가 어떤 키를 선택하더라도 평균적으로 좋은 성능을 낸다.
완전 해싱
: 검색을 위해 필요한 최악의 경우 메모리 접근 횟수가 O(1)인 해싱 방법
