[TIL] 자료구조5 - 해시 테이블

해시 테이블

 

-가장 유용한 자료 구조중 하나

 

 

 

1. 가게에서 물건의 가격 찾을때 빨리 찾는 순서는?

 

-> 모든 가격표를 외운 알바생  >  정렬된리스트  > 정렬되지 않은 리스트

 

 

 

2. 가게에서 물건의 가격 찾을때 빨리찾는 순서와 시간복잡도는?

 

-> 모든 가격표를 외운 알바생(O(1))  >  정렬된리스트(이진 탐색) (O(log n))  >  정렬되지 않은 리스트(단순 탐색)(O(1))

 

 

 

 

가격을 외운 알바생을 만드는 법 : 해시 함수

 

 

해시테이블은 언제 사용해야할까?

-> 해싱은 특정 데이터가 "들어온 순서 상관 없이" 삽입, 삭제, 검색이 자주 발생하는 경우에 사용하기에 좋다.

 

 

해시함수 조건 

 

1. 일관성을 가져야한다

 

같은 문자를 넣었을때는 항상 같은 값이 나와야만 한다

 

ex)

 

apple을 넣었을때 "4"가 나왔다면  apple을 넣으면 항상 "4"만 나와야 한다

 

 

2.다른 단어가 들어가면 다른 숫자가 나와야한다

 

이상적인 경우에, 서로 다른 단어에 대해 모두 서로 다른 숫자가 나와야만 한다

 

 

 

 

 

 

해시 함수 만들기)

 

apple -> 해시함수 -> 3

(배열 인덱스3에 apple 가격 0.67 기입)

 

milk -> 해시함수 -> 0

(배열 인덱스0에 milk 가격 1.49 기입)

 

avocado -> 해시함수 -> 4

(배열 인덱스4에 avocado 가격 1.49 기입)

 

 

 

 

나중에 avocado의 가격이 필요할때 배열을 탐색할 필요가 없다

avocado를 해시함수에 넣기만하면 4가 나오고 배열 인덱스4를 확인하면된다

그럼 1.49값 출력

 

 

 

 

해시함수의 특징

 

1. 해시함수는 같은이름에 대해서 같은 인덱스만 할당해야한다.

 

apple을 해시함수에 넣을때마다 항상 같은 값이 나와야만 한다.

 

처음에 저장할때와 저장위치를 찾을때 해시함수를 둘다 쓰기 때문이다.

 

 

 

 

2.해시함수는 다른 문자열에 대해서는 다른 인덱스를 할당한다.

 

avocado에 인덱스4가 할당되었다면 milk에는 다른 인덱스가 할당되어야 한다

 

 

 

 

-해시 함수는 배열의 크기를 알고있어야 한다.

 

왜냐면 유효한 인덱스만 반환해야하기 때문이다. 배열이 5개짜리인데 인덱스 10을 할당할 수는 없다

 

 

 

 

-해시 함수와 배열을 합치면 해시 테이블을 얻을 수 있다.

 

- 배열과 리스트는 직접 메모리를 할당하지만 해시 테이블은 해시 함수를 이용해서 어디에 원소를 저장할지 결정한다

 

 

 

해시테이블 예시)

 

전화번호부,  웹사이트 ip주소,  캐싱

 

 

전화번호부는 같은 이름이면 항상 같은 번호가 조회되고, 다른 이름이면 다른 번호가 조회됨.

 

각각의 웹사이트는 해시함수를 거쳐 같은 웹사이트는 같은 ip주소를,다른 웹사이트들은 각기다른 ip주소 값을 가져야한다.

 

 

 

 

 

-충돌

 

: 서로다른 키값이 같은 위치에 할당되는 경우

 

충돌은 해시 테이블의 성능을 떨어뜨리기 때문에 해결해야한다.

 

만약 충돌이 생기게 되면, 같은 공간에 키값들을 연결 리스트로 만들어 넣는다.

 

ex)

단어들을 맨 앞글자를 기준으로 할당한다고 했을 떄, apple과 avocado는 같은 위치에 할당되게 된다.

 

연결리스트 :  <apple : 0.67> -> <avocado : 1.49>

 

 

 

-이상적으로는 해시 함수는 키를 해시 테이블 전체에 고르게 할당해야한다. 

(좋은 해시함수는 해시테이블 전체에 키를 고르게 할당한다)

 

-연결리스트가 길어지면 해시테이블의 속도도 느려진다

(해시 테이블이 점점 연결리스트로 되어가므로)

 

 

-해시테이블의 평균 소요시간은 O(1)이다

이것은 순간적이라는 뜻이 아니라, 상수시간으로, 항상 똑같은 시간이 소요된다는 의미이다

데이터의 수가 많아져도 같은 시간이 소요된다.

하지만 최악의 경우, 해시테이블도 모든 항목이 같은 공간에 할당되어 모든 요소가 연결리스트로 연결되면, O(n)의 시간이

소요된다

 

단순 탐색은 선형시간 (O(n))이 소요된다.

 

이진 탐색은 로그시간(O(log n))이 소요된다.

 

 

충돌을 피하려면 1.낮은 사용률 2.좋은 해시 함수가 필요하다

 

 

 

1. 사용률

 

사용률은 ( 해시테이블에 있는 항목의 수 / 전체 해시 테이블 공간의 수)이다.

 

ex)

-배열크기 5인데, 2개의 값이 들어있다면 사용률은 (2 / 5 = 0.4) 0.4이다

 

-배열크기 3인데, 1개의 값이 들어있다면 사용률은 (1 / 3 = 0.33) 0.33이다

 

 

사용률이 1보다 크면 배열내 공간 수보다 항목 수 가 많다는 것을 의미한다.

 

사용률이 커지기 시작하면 해시 테이블의 공간을 추가해야하는데 이를 "리사이징" 이라고 한다.

 

보통 사용률이 0.7보다 커지면 리사이징을한다.

 

사용률이 낮을수록 충돌이 적게 일어나고 해시 테이블의 성능도 좋아진다.

 

충돌을 최대한 피하기위해 들어갈 최대 데이터의 크기보다 3~4배 크게 만드는것이 좋다

 

 

2.해시 함수

 

좋은 해시함수란 배열에 값을 고르게 분포시키는 함수

 

 

 

 

 

 

[2023_01][산업정보화][실습]_5_해시_테이블.ipynb

1.33MB