데이터 구조 - 분리 링크 로 충돌 문 제 를 해결 하 는 산 목록
변량
private List[] theLists; //체인 헤더 의 배열 private int currentSize; /산 목록 의 원소 개수 private static int DEFAULTSIZE = 101; //기본 산 목록 크기 private static float LOADFACTOR = 0.75f; /로 딩 인자
구조 기
public SeparateChainingHashTable(){
this(DEFAULT_SIZE);
}
@SuppressWarnings("unchecked")
public SeparateChainingHashTable(int size){
theLists = new LinkedList[nextPrime(size)];
for(int i=0; i < theLists.length; i++)
theLists[i] = new LinkedList<T>();
currentSize = 0;
}
산열 함수
hash (): 해시 함수, 요소 x 의 산 목록 을 계산 하여 요소 가 있 는 링크 의 위 치 를 얻 습 니 다.해시 값 을 계산 하 는 것 은 넘 칠 수 있 는 상황 이 므 로 여기 서 작은 처 리 를 하 였 습 니 다.이곳 의 해시 함 수 는 간단 한 실현 일 뿐 더욱 효과 적 인 해시 함 수 를 실현 함으로써 요소 가 산 목록 에서 의 분 포 를 더욱 고 르 게 할 수 있다.
private int hash(T x){
int hashVal = x.hashCode();
hashVal %= theLists.length;
if(hashVal < 0)
hashVal += theLists.length;
return hashVal;
}
rehash (): 중 산열 함수.산 목록 의 요소 비율 이 로 딩 인 자 를 초과 하면 산 목록 의 액세스 효율 을 확보 하기 위해 서 는 산 목록 을 확장 하고 요소 의 재 산열 을 해 야 합 니 다.이렇게 하면 같은 해시 코드 를 가 진 요소 가 너무 많아 서 해당 링크 가 너무 길 고 요소 의 조회 효율 을 낮 출 수 있다.중 산열 함 수 는 주로 두 가지 작업 을 진행 합 니 다. 1. 산열 표 크기 의 확장 을 진행 합 니 다.2. 원 산 목록 의 요 소 를 다시 산열 합 니 다.
private void rehash(){
List<T>[] oldList = theLists;
currentSize = 0;
/* */
theLists = new LinkedList[nextPrime(2 * oldList.length)];
for(int i=0; i < theLists.length; i++)
theLists[i] = new LinkedList<T>();
/* */
for(int i=0; i < oldList.length; i++){
for(T x : oldList[i])
insert(x);
}
}
함수.
clear (): 해시 시 계 를 빈 시계 로 초기 화 합 니 다.
public void clear(){
for(int i=0; i < theLists.length; i++)
theLists[i].clear();
currentSize = 0;
}
nextPrime (): n 보다 큰 최소 소 수 를 가 져 옵 니 다.isPrime (): n 이 소수 인지 판단 합 니 다.여기 서 하나의 기 교 를 사 용 했 는데 연구 에 의 하면 산열 표 의 크기 가 소수 라면 원소 가 산 열 된 후의 분포 가 비교적 고르다 고 한다.(구체 적 으로 stackoverflow 의 설명 을 참고 할 수 있 습 니 다)
private static int nextPrime(int n){
while(!isPrime(n))
n++;
return n;
}
private static boolean isPrime(int n){
if(n < 2)
return false;
else{
for(int i=2; i < Math.sqrt(i); i++)
if(n%i == 0)
return false;
}
return true;
}
contains (): 조회 표 에 요소 x 가 포함 되 어 있 는 지 확인 합 니 다.해시 코드 를 통 해 해당 하 는 링크 를 얻 을 수 있 고 링크 의 contains 방법 을 통 해 요 소 를 찾 을 수 있 습 니 다.
public boolean contains(T x){
List<T> whichList = theLists[hash(x)];
return whichList.contains(x);
}
insert (): 요소 x 삽입.요 소 를 삽입 하 는 작업 은 대부분 비용 이 적 습 니 다 (O (1). 해시 코드 를 계산 하고 해당 하 는 링크 에 요 소 를 추가 하면 되 기 때 문 입 니 다.아주 적은 경우 에 만 표 의 요소 비례 가 로드 인자 의 한계 에 이 르 렀 고 표 에 대해 재 산열 작업 을 해 야 한다. 이 럴 때 불가피 한 비용 이 많이 든다 (O (N).
public void insert(T x){
/* */
List<T> whichList = theLists[hash(x)];
/* ， */
if(!whichList.contains(x)){
whichList.add(x);
/* 0.75， ， */
if(++currentSize == (int)(theLists.length * LOADFACTOR))
rehash();
}
}
remove (): 요소 x 를 삭제 합 니 다.요소 x 를 삭제 하 는 것 은 매우 간단 합 니 다. 해시 코드 만 계산 한 후에 해당 하 는 링크 에서 요소 x 가 존재 하 는 지 찾 고 존재 하면 삭제 합 니 다.
public void remove(T x){
List<T> whichList = theLists[hash(x)];
if(!whichList.contains(x)){
whichList.remove(x);
currentSize--;
}
}
소스 코드
import java.util.LinkedList;
import java.util.List;
/** * * equals(),hashCode() 。 * @author Bingo * * @param <T> */
public class SeparateChainingHashTable <T>{
public SeparateChainingHashTable(){
this(DEFAULT_SIZE);
}
@SuppressWarnings("unchecked")
public SeparateChainingHashTable(int size){
/* list , */
theLists = new LinkedList[nextPrime(size)];
for(int i=0; i < theLists.length; i++)
theLists[i] = new LinkedList<T>();
currentSize = 0;
}
/** * */
public void clear(){
for(int i=0; i < theLists.length; i++)
theLists[i].clear();
currentSize = 0;
}
/** * x * @param x * @return x true， false */
public boolean contains(T x){
List<T> whichList = theLists[hash(x)];
return whichList.contains(x);
}
/** * x * @param x */
public void insert(T x){
/* */
List<T> whichList = theLists[hash(x)];
/* ， */
if(!whichList.contains(x)){
whichList.add(x);
/* 0.75， ， */
if(++currentSize == (int)(theLists.length * LOADFACTOR))
rehash();
}
}
/** * x * @param x */
public void remove(T x){
List<T> whichList = theLists[hash(x)];
if(!whichList.contains(x)){
whichList.remove(x);
currentSize--;
}
}
private List<T>[] theLists;
private int currentSize;
private static int DEFAULT_SIZE = 101;
private static float LOADFACTOR = 0.75f;
/** * , x * @param x * @return */
private int hash(T x){
int hashVal = x.hashCode();
hashVal %= theLists.length;
if(hashVal < 0)
hashVal += theLists.length;
return hashVal;
}
/** * , , */
@SuppressWarnings("unchecked")
private void rehash(){
List<T>[] oldList = theLists;
currentSize = 0;
/* */
theLists = new LinkedList[nextPrime(2 * oldList.length)];
for(int i=0; i < theLists.length; i++)
theLists[i] = new LinkedList<T>();
/* */
for(int i=0; i < oldList.length; i++){
for(T x : oldList[i])
insert(x);
}
}
/** * n * @param n * @return */
private static int nextPrime(int n){
while(!isPrime(n))
n++;
return n;
}
/** * ( ) * @param n * @return */
private static boolean isPrime(int n){
if(n < 2)
return false;
else{
for(int i=2; i < Math.sqrt(i); i++)
if(n%i == 0)
return false;
}
return true;
}
}
참고 자료
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
