컴퓨터 알고리즘 초급 #8 ( 해쉬 알고리즘 1 )

 

Direct-address Tables 

- 크기가 |U|인 테이블 T를 생성하고 key k를 slot k에 저장하는 방식

- 중복되는 key가 없다고 가정 

 

 

이러한 테이블의 장점은 키 값만 알면 데이터를 바로 찾을 수 있으므로 시간복잡도가 엄청나게 빠르다 .O(1)

 

Direct addressing의 공간 복잡도

- O(|U|)

- 실제 공간 사용을 전체 공간으로 나눈 |K|/|U|를 적재율이라고 한다.

- 만약 적재율이 낮다면, 실제로 대부분의 공간은 낭비된다.

 

Hash Tables

 

해쉬함수라는 것은 임의의 크기의 데이터를 받아서 그 데이터를 고정된 크기로 바꿔주는 것을 해쉬라고 부른다.

 

 

 

actual keys를 어떠한 해쉬함수에 넣어서 거기에 해당하는 해쉬값에 넣어준다.

 

문제점은 동일한 해쉬값이 생길 수 있다. ( 하나의 해쉬에 저장될 수도 있다. 다이렉트 테이블은 학생 수만큼 공간을 만들어주지만, 해쉬테이블은 각 학년에 50명이 있다면, 150개의 좌석이 아닌, 50개의 좌석만 만들어줘서 각 번호에 맞는 사람만 사용할 수 있게 해주는 느낌, 이 상황에서 1학년과 2학년의 같은 번호인 사람이 동시에 사용한다면 문제가 생긴다. 이것을 퀄리전 이라고 부른다.)

 

 

 

충돌이 일어나면, 링크드 리스트를 이용해서 해결해준다.

 

하지만, 이렇게하면 시간복잡도가 늘어난다. ( 특정 슬롯에서 연결리스트 탐색을 해야하기 때문 )

 

 

 

해쉬테이블 자체는 공간의 효율성을 올리기 위해서 만들어졌다.

 

대신 충돌이라는 문제가 발생을 해서, 시간복잡도에 대한 문제가 생겼다.

 

 

 

대표적인 해쉬함수 , 나머지를 이용한 해쉬 함수

 

 

 

 

나머지 해쉬함수를 쓰고 싶으면, 나누는 값을 2의 지수승과 먼 소수를 선택하자.