자바 오픈 주소 법 과 체인 주소 법 으로 hash 충돌 을 해결 하 는 방법 예시
먼저 그림 한 장 을 보고,
이 그림 에서 알 수 있 듯 이 hashMap 은 하나의 배열 을 유지 하고 배열 안의 모든 단원 은 하나의 링크 입 니 다.그러면 왜 hash 충돌 이 발생 합 니까?이것 이 바로 다음 에 토론 해 야 할 문제 다.
배열 이기 때문에 반드시 길이 가 있 을 것 입 니 다.우리 가 배열 에 데 이 터 를 삽입 할 때 어떤 유형의 데이터 든 배열 에 있어 서 특정한 아래 표 에 대응 하 는 공간 을 차지 하 는 것 입 니 다.그러면 가입 한 데이터 가 점점 많아 질 때 여러 개의 데이터 가 같은 위 치 를 차지 하 는 것 이 아 닙 니까?답 은 긍정 적 이다.이것 이 바로 hash 충돌 이 발생 하 는 원시 적 인 요소 이다.
먼저,우 리 는 몇 가지 개념 을 알 아 보 겠 습 니 다.hashMap 또는 다른 유사 한 map 에 있어 서 우리 가 안에 데 이 터 를 추가 할 때 배열 에 직접 추가 하 는 것 이 아니 라 이 데 이 터 를 삽입 하 는 hash 값 을 계산 하 는 것 입 니 다.즉,hash 알고리즘 을 통 해 이 값 을 추가 한 다음 에 데 이 터 를 찾 을 때 hashMap 역시 당신 의 key 에 따라이 hash 값 을 거꾸로 내 놓 고 데 이 터 를 꺼 냅 니 다.즉,이 hash 값 은 삽입 값 에 대응 하 는 배열 아래 표 로 이해 할 수 있 습 니 다.
그러나 실험 을 통 해 알 수 있 듯 이 hash 함수 가 서로 다른 key 를 계산 할 때 같은 hash 값 을 얻 을 수 있 습 니 다.그러면 이 hash 값 을 배열 의 표지 로 사용 하면 이 값 의 아래 표 시 를 찾 을 수 없습니다.이때 충돌 이 발생 합 니 다.
다음은 개발 주소 법 으로 hash 충돌 문 제 를 해결 하 는 코드 를 모 의 해 보 겠 습 니 다.먼저 대상 을 정의 합 니 다.여 기 는 Info 입 니 다.실제 장면 에 더욱 가 까 워 지기 위해 서 여기 있 는 속성 은 모두 문자열 입 니 다.
개방 주소 법 은 무엇 입 니까?
충돌 이 발생 했 을 때 배열 의 빈 자 리 를 찾 아 데 이 터 를 삽입 하고 hash 함수 로 획득 수의 아래 표 시 를 계산 하지 않 습 니 다.이 방법 을 개발 주소 법 이 라 고 합 니 다.
public class Info {
private String key; // ，
private String name; //
public Info(String key, String name) {
this.key = key;
this.name = name;
}
public String getKey() {
return key;
}
public void setKey(String key) {
this.key = key;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
}
/**
* hashMap
*
*/
public class HashTable {
private Info[] arr;
/**
*
*/
public HashTable() {
arr = new Info[100];
}
/**
*
*/
public HashTable(int maxSize) {
arr = new Info[maxSize];
}
/**
*
*/
public void insert(Info info) {
//
String key = info.getKey();
//
int hashVal = hashCode(key);
// ，
while(arr[hashVal] != null && arr[hashVal].getName() != null) {
// ，
++hashVal;
//
hashVal %= arr.length;
}
arr[hashVal] = info;
}
/**
*
*/
public Info find(String key) {
int hashVal = hashCode(key);
while(arr[hashVal] != null) {
if(arr[hashVal].getKey().equals(key)) {
return arr[hashVal];
}
++hashVal;
hashVal %= arr.length;
}
return null;
}
/**
*
*/
public Info delete(String key) {
int hashVal = hashCode(key);
// ， hashVal ， null
while(arr[hashVal] != null) {
if(arr[hashVal].getKey().equals(key)) {
Info tmp = arr[hashVal];
tmp.setName(null);
return tmp;
}
++hashVal; // ， ，
hashVal %= arr.length;
}
return null;
}
/**
* hash ，
*/
public int hashCode(String key) {
BigInteger hashVal = new BigInteger("0");
BigInteger pow27 = new BigInteger("1");
for(int i = key.length() - 1; i >= 0; i--) {
int letter = key.charAt(i) - 96;
BigInteger letterB = new BigInteger(String.valueOf(letter));
hashVal = hashVal.add(letterB.multiply(pow27));
pow27 = pow27.multiply(new BigInteger(String.valueOf(27)));
}
return hashVal.mod(new BigInteger(String.valueOf(arr.length))).intValue();
}
}안에 이해 하기 어 려 운 부분 이 있 습 니 다.바로 데 이 터 를 삽입 할 때 우 리 는 while 순환 으로 삽입 합 니 다.개발 주소 인 만큼 배열 의 모든 유 휴 공간 을 우 리 는 사용 할 수 있 습 니 다.전 제 는 이 위치 가 다른 값 에 의 해 점용 되 지 않 았 다 는 것 입 니 다.배열 이 연속 적 이기 때문에 우 리 는 순환 적 으로 이런 위 치 를 찾 아야 합 니 다.그래서++hashVal 이라는 코드 가 있 습 니 다.빈 자 리 를 찾 을 때 까지 데 이 터 를 삽입 합 니 다.
테스트 main 방법 을 실행 합 니 다.우 리 는 데이터 가 성공 적 으로 삽입 되 었 음 을 보 았 습 니 다.그러나 hash 함 수 를 통 해 계산 한'a'와'ct'는 똑 같 습 니 다.앞에서 말 한 문 제 를 다시 한 번 입증 하 였 습 니 다.
이상 은 바로 개발 주소 법 으로 hash 충돌 을 해결 하 는 해결 방법 을 말 한 것 입 니 다.그러나 이렇게 하면 만전 을 기 할 수 있 습 니까?
우 리 는 데이터 의 길이 가 유한 하 다 는 것 을 고려 해 보 겠 습 니 다.그러나 우 리 는 배열 에 많은 데 이 터 를 추가 할 수 있 습 니 다.배열 은 항상 채 워 질 때 가 있 습 니 다.그러면 주소 법 을 개발 하 는 것 도 소 용이 없습니다.물론 실제 업무 에서 데이터 의 크기 를 예측 할 수 있다 면 우 리 는 이런 방식 으로 일부 문 제 를 해결 할 수 있 습 니 다.문 제 는 이렇다.확실한 해결책 은 아니다.
더 적합 한 방법 은 무엇 일 까요?사실은 hashMap 에서 비교적 많은 체인 주소 법 을 사 용 했 습 니 다.즉,처음에 우리 그림 에서 보 여 준 것 입 니 다.기본 구 조 는 아직도 하나의 배열 입 니 다.그러나 배열 의 모든 단원 이 하나의 데이터 가 아니 라 하나의 링크 입 니 다.즉,linkedList 와 같은 구조 입 니 다.새로 삽 입 된 여러 데 이 터 는 hash 함 수 를 계산 하여 같은 배열 아래 표 시 를 얻 었 을 때우 리 는 이 색인 위치 에서 유지 하 는 링크 에 값 을 삽입 하면 됩 니 다.무엇이 체인 주소 법 입 니까?
**
hash 표 의 각 단원 에 링크 를 설정 합 니 다.삽입 할 데이터 항목 의 키 워드 는 보통 hash 표 의 한 단원 에 투사 되 고 데이터 항목 자 체 는 이 단원 이 유지 하 는 링크 에 삽 입 됩 니 다.
**
다음은 코드 로 이 과정 을 실현 하 겠 습 니 다.위의 모든 것 과 다른 것 은 링크 중의 구 조 는 우리 가 관리자 의 한 노드,즉 Node 를 통 해 링크 구조 에 익숙 하지 않 은 학생 들 이 먼저 스스로 바 이 두 를 할 수 있 습 니 다.어렵 지 않 습 니 다.
1.대상 Info 를 정의 합 니 다.
public class Info {
private String key;
private String name;
public Info(String key, String name) {
this.key = key;
this.name = name;
}
public String getKey() {
return key;
}
public void setKey(String key) {
this.key = key;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
}
public class Node {
//
public Info info;
// ,
public Node next;
public Node(Info info) {
this.info = info;
}
}
/**
* linkedList
*
* @author asus
*
*/
public class LinkList {
//
private Node first;
public LinkList() {
first = null;
}
//
public void insertFirst(Info info) {
Node node = new Node(info);
node.next = first;
first = node;
}
// ，
public Node deleteFirst() {
Node temp = first;
first = temp.next;
return temp;
}
/**
*
*/
public Node find(String key) {
Node current = first;
while (!key.equals(current.info.getKey())) {
if (current.next == null) {
return null;
}
current = current.next;
}
return current;
}
/**
*
*/
public Node delete(String key) {
Node current = first;
Node previous = first;
while (!key.equals(current.info.getKey())) {
if (current.next == null) {
return null;
}
previous = current;
current = current.next;
}
if (current == first) {
first = first.next;
} else {
previous.next = current.next;
}
return current;
}
}
public class HashTable {
private LinkList[] arr;
/**
*
*/
public HashTable() {
arr = new LinkList[100];
}
/**
*
*/
public HashTable(int maxSize) {
arr = new LinkList[maxSize];
}
/**
*
*/
public void insert(Info info) {
String key = info.getKey();
// hash
int hashVal = hashCode(key);
if (arr[hashVal] == null) { // ， linkList
arr[hashVal] = new LinkList();
}
arr[hashVal].insertFirst(info);
}
/**
*
*/
public Info find(String key) {
int hashVal = hashCode(key);
return arr[hashVal].find(key).info;
}
/**
*
*/
public Info delete(String key){
int hashVal = hashCode(key);
return arr[hashVal].delete(key).info;
}
/**
* hash
*/
public int hashCode(String key) {
BigInteger hashVal = new BigInteger("0");
BigInteger pow27 = new BigInteger("1");
for (int i = key.length() - 1; i >= 0; i--) {
int letter = key.charAt(i) - 96;
BigInteger letterB = new BigInteger(String.valueOf(letter));
hashVal = hashVal.add(letterB.multiply(pow27));
pow27 = pow27.multiply(new BigInteger(String.valueOf(27)));
}
return hashVal.mod(new BigInteger(String.valueOf(arr.length))).intValue();
}
}
다음 에 우리 가 테스트 를 해 보면 아직도 효 과 를 얻 었 다 는 것 을 알 수 있다.이 는 우리 가 모 의 한 체인 주소 법 도 효력 이 발생 했다 는 것 을 의미한다.
이상 은 주소 법 과 체인 주소 법 을 개발 하여 hash 충돌 을 해결 하 는 두 가지 방식 입 니 다.hashMap 의 바 텀 원 리 를 이해 하 는 데 도움 이 되 기 를 바 랍 니 다.시청 해 주 셔 서 감사합니다.많은 응원 부 탁 드 리 겠 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Is Eclipse IDE dying?In 2014 the Eclipse IDE is the leading development environment for Java with a market share of approximately 65%. but ac...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
