hash3 [Java] HashMap Hashtable 차이점, 구분하기 1. Hash란? 해시(Hash)란 단방향 암호화 기법인 해시함수(HashFunction)을 이용하여 생성된 고정된 길이의 비트열을 의미합니다. Hash function, 해시 함수 (짧게는 해시 라고도 부름)는 임의의 길이를 갖는 임의의 데이터를 고정된 길이의 데이터로 매핑하는 단방향 함수를 의미합니다. 다른말로 표현하자면, 아무리 큰 숫자를 넣더라도 정해진 크기의 숫자가 나오는 함수입니다. 예를 들면 어떤 숫자를 10으로 나누었을 때 그 나머지를 구하는 함수도 해시 함수입니다. (나머지가 0~9 까지 한자리의 크기로 출력되기 때문) 이러한 해시 함수를 적용하여 나온 고정된 길이의 값을 해시값, 해시 코드, 해시섬(sum) 등으로 부릅니다. 해시 함수는 보통 입력의 범위(정의역)보다 출력값의 범위(치역.. 2023. 12. 30. 재해싱 체인을 사용하면 자료구조가 찰수록 λ는 1보다 큰 수가 됩니다. 그렇기 때문에 크기 조정이 필요합니다. 크기가 2배인 배열을 만듭니다. 아래 코드에 따라 data의 index를 다시 결정하여 연결 리스트의 요소들을 옮깁니다. // data의 index 결정 int idx = x.hashCode(s); idx = idx & ox7FFFFFFF; idx = idx % tableSize; 크기를 두배로 하면서 리스트의 위치를 새로운 배열에 그대로 옮기면 정보를 다시 찾고나 제거할때 올바른 위치를 찾을 수 없습니다. 그렇기 때문에 각 요소의 위치를 초기화 한 후, 처음부터 위치를 다시 지정해주어야합니다. 2023. 8. 7. 체이닝 (Chaining) 해시를 공부하다가 접한 문제인데, 해시는 사실상 배열 한 개에 요소가 추가되어서 만들어지는 것입니다. 체이닝은 이 배열의 위치마다 새로운 자료구조를 만들어 수많은 데이터를 수용할 수 있도록 만들어 줍니다. 체이닝 충돌을 피하기 위해 체인을 사용하는 방법이 있습니다 체인을 만들기 위해 우선 배열을 만들고 그 위치마다 리스트를 만들어 줍니다. [{ob1-1:dd,ob1-2:dd....}, {ob2-1:dd, ob2-2:dd....}, {ob3-1:dd, ob3-2:dd...}...] 이런느낌 위 그림과 같이 배열마다 리스트를 만들어주고, 자리가 찰때마다 add를 해줄 수 있습니다. 이렇게 체이닝을 하면 수용가능한 요소 개수에 제한이 없어지고 크기 조정도 자주 할 필요가 없어집니다. 적재율 λ는 항목의 개수를.. 2023. 8. 7. 이전 1 다음
