JS Hash Table

해쉬테이블: 해쉬 함수를 사용하여 키 값을데이터 공간의 주소로 변환하고 해당 주소에 키 값에 대응하는 데이터를 넣는 자료구조를 말한다. (ex alice라는 문자열을 해쉬함수를 통하여 1번으로 정하는 것)

- 장점: 중복 데이터를 찾기 쉽다, 빠른 탐색,삽입,삭제속도, 어떤 항목과 다른 항목의 관계를 모형화하기 좋다.

- 단점: 공간의 효율성이 낮다.

(2개의 데이터를 넣는다고 해도 10개의 공간을 만들어 놔야한다. 내가 삽입할 자료의 크기보다 훨씬 큰 데이터 공간을 미리 만들고 시작하기 때문에 공간 효율성이 낮고, 11개를 넣게 되면 overflow가 발생한다.

해시 함수의 의존도가 높기 때문에 해시 함수의 성능이 떨어지거나 원하는대로 작동하지 않는다면 성능과 효율이 떨어진다.

해시 테이블의 충돌: 성능이 뛰어난 자료구조이지만 다른 키 2개를 해시 함수에 넣었는데 같은 주소 값이 나오는 경우를말한다.

해결방법

1. Linked List: 같은 주소가 나왔을 때 해당 주소에 이미 데이터가 있다면 그 데이터에 연결 리스트로 연결하는 방법이다.

-(ex: 알파벳을 0~25의 숫자에 대응 시킨후, 영어단어를 입력하면 맨 앞글자에 해당 숫자를 output으로 넘겨주는 해싱함수가 있다고 가정 할때.

A로 시작하는 모든 사람은 같은 주소값을 갖는다. 그래서 a로 시작하는 모든 친구의 데이터를 연결 리스트로 연결한다.

-단점: 연결 리스트가 길어질 수록 성능이 낮아진다. 연결 리스트가 길어지면 리스트를 순회하는 과정 탓에 성능이 떨어진다.

2. Linear probing(선형 탐사): 충돌이 발생한 지점의 다음 방부터 탐사하여 빈 방이 있으면 그 공간에 데이터를 넣는다.

끝까지 탐색했는데 빈 공간이 없으면 맨 처음으로 돌아가 다시 검사한다. 주변에 데이터공간이 비어있지 않다면 빈 공간을 위해 모든 공간을 탐색해야한다.

Bio o(충돌 없을 시)

데이터를 추가할때 해시 함수에 key를 넣어 주소를 알아낸 후 해당 주소에 데이터를 삽입하면 된다.O(1)의 상수 시간으로 표기 할 수 있다.

데이터를 검색하거나 삭제할 때도 마차가지이다.

상수시간이란: 해시 테이블의 크기와 상관없이 항상 똑같은 시간이 걸린다는 뜻이다. 단순탐색으로 데이터를 검색한다면 앞에서 부터 검색을 해야해서 O(n)만큼 소요된다.

최악의 경우 해시 테이블은 데이터의 탐색,삽입,삭제가 모두 O(n)만큼의 시간이 소요된다.

Load Factor(사용률)

해시 테이블에서 사용률이란 해시 테이블의 공간을 얼마나 사용하고 있는지 수식으로 나타낸 것.

해시 테이블에 저장된 항목수 / 해시 테이블 공간 수

배열에서 5개의 방이 있는데 그 중 2개의 공간에 데이터가 저장되어 있다면 2/5 = 0.4가 사용된다.

1보다 큰 것은 테이블의 공간이 부족하다는 뜻.

사용률이 0.7이상이면 해시 테이블을 리사이지 하는데 대략 2배 정도의 크기로 배열을 만든다.

리사이징을 하여 배열을 크게 만들고 나면 해시 함수를 사용하여 기존 테이블에 있던 데이터를 새로운 해시 테이블에 다시 저장해야한다. 좋지않다.

해싱: 어떤 길이든지 상관없이 input string을 받아 고정된 길이의 결과물로 만들어주는 것.

해싱함수: 동일한 input이 들어가면 동일한 output 나와야한다.

-값이 골고루 분포되어야한다.

웹 개발