해시 테이블이란?
해시 테이블은 연관배열 추가에 사용되는 자료구조이다.데이터를 효율적으로 관리 및 유자하는데 사용된다.먼저 연관배열에 대해 알아보자. 일반적으로 숫자를 key로 값을 뽑을 수 있으면 연관배열이라고 한다. 배열의 키를 이용하여 키와 값으로 나누어 키 값의 모음을 사용하는 것, 이것을 연관배열이라고 한다.
해시 테이블의 장점
- 해시 테이블을 사용하면 속도를 빠르게 O(1) 로 처리할수 있다.
- 데이터를 횽ㄹ적으로 관리 및 유지할수 있다.
해시 테이블의 해시 함수란?
똑같은 데이터가 들어올때마다 똑같이 분류되야 하는 규칙성의 정의 이다.
해시 함수의 특징
- array의 길이 내의 값만 반환시킬수 있어야 한다.
- 언제든지 값을 넣었을 때 같은 인덱스 값이 나와야한다.
- 해시함수는 어떠한 저장도 할수없고 그때그때 값을 넣어주면 값을 뱉어주는 함수이다.
해시테이블의 흐름
input으로 데이터가 들어오게 되면 해시 함수를 거쳐 인덱스를 가르키는 값을 반환한다. 그 값을 가지고 배열에 인덱스에 해싱한 값을 넣어준다.
해시함수의 충돌?
해시함수를 제작할 때 중요한점은 충돌이다. 예를 들어 input의 데이터가 해시함수를 거쳐 나온값이 같으면 하나의 배열에 들어가게 되는데 이미 값이 있는 배열은 값을 저장하지 못하게 된다. 이렇게 중복된 해시값을 배열에 저장하기 위해서는 충돌을 해결해 주어야한다.
충돌해결 방법
- chaning : linkedList 를통해 칸을 늘려준다. 그리고 찾기위해 값이 들어왔을 때 해쉬함수를 통해 인덱스 값으로 변환이 되고 그 값과 일치하는 인덱스에 값중 인풋과 같은 키 값을 찾아 들어가 키와 값을 출력하면 된다.
- linear probing:이미 만들어 놓은 버켓을 (값의 칸) 을 미리 소모하는 방법 해당 인덱스에 값이 차있으면 다른 버켓에 밀어넣는법 배열이 가득 차면 길이를 늘려준다.
Property
storage: array
buckets: 각 storage의 collision
tuples : 각 버켓이 갖고 있는 데이터Methode
insert(): 해시함수를 거칠 데이터
retrieve(): 해당 인덱스의 값을 검색
remove(): 해당 인덱스의 키 값을 제거pseudo code
insert() //해시함수에 들어갈 값, 일정한 패턴에 위해 인덱스길이 내 수로 반환
retrieve() // 해시함수를 거쳐 나온 인덱스의 값을 찾아 검색
remove()// 해시함수를 거쳐 나온 값중 해당 값을 제거해줌
//1.해시함수에 들어온 값이 어떠한 조건에 위하여 배열 길이내 값으로 반환
//2.반환된 값의 인덱스에 버켓에 값을 저장.
//3.겹치는 값이 나왔을 경우 버켓을 추가해주고 리스트로 이어준다.
//4.검색할 값이 해시함수를 거쳐 해당 인덱스를 찾았을때 안에 있는값 반환
//5. if 안에 많은 버켓이 있다면 인풋 값과 동일한 값을 내보내 준다.
//종료