간단 한 Hash 데이터 구조 구현

1. 이전에 배 운 간단 한 데이터 구조 에 대한 회고  프로그램 언어 를 배 울 때 배열 은 우리 가 먼저 접 하 는 데이터 구조 이다.알다 시 피 배열 은 데이터 에 접근 할 때 아래 표 시 를 통 해 빠 른 접근 데 이 터 를 사용 할 수 있 지만 삭제 와 삽입 할 때 배열 이 좋 지 않 습 니 다.  링크 는 데이터 의 삭제 와 삽입 에 편리 하지만 데이터 에 대한 빠 른 접근 에 이 르 지 못 합 니 다.  그렇다면 이들 을 종합 한 데이터 구 조 는 없 을 까?  답 은 긍정 적 이다.예 를 들 어 Hash 데이터 구 조 는 배열 의 장점 을 가지 고 링크 의 장점 을 실현 할 수 있다.  그러면 우 리 는 Hash 가 무엇 인지 간단하게 소개 하고 간단 한 Hash 구 조 를 실현 합 니 다.          Hash 의 간단 한 소개  Hash: Hash 는 임의의 길이 의 입력 을 해시 알고리즘 을 통 해 고정 길이 의 출력 을 얻 는 것 입 니 다. 이 출력 은 해시 값 입 니 다.그 중에서 해시 값 을 얻 는 방법 은 매우 해시 함수 이다.해시 함 수 는 저장 요소 의 저장 위 치 를 얻 을 수 있 습 니 다.    예 를 들 어 배열 에 데이터 200 을 저장 하고 200 을 배열 의 요소 값 으로 저장 하면 (예 를 들 어 array [i] = 200) 을 찾 을 때 배열 을 옮 겨 다 니 며 특정한 위치 가 200 인지 판단 해 야 한다.
이런 저장 방법 은 데이터 가 비교적 많 을 때 시간 을 낭비 할 수 있다.    그러면 우 리 는 특정한 함 수 를 통 해 이 요소 가 있 는 위치 에 있 는 색인 을 얻 을 수 있 습 니 다. 그러면 찾 을 때 이 색인 위치 에 있 는 데이터 만 얻 으 면 됩 니 다.    예 를 들 면:            int index = H (저 장 된 요소);    그 중에서 index 는 바로 얻 기 위 한 색인 입 니 다.이 함 수 는 해시 함수 이다.    자주 사용 하 는 구조 산열 함수 의 방법 은 다음 과 같다.     1: 직접 주소 지정 법     2: 디지털 분석 법     3: 제곱 취 중 법     4: 접 는 법     5: 랜 덤     6: 남 은 것 을 제외 하고 남 은 것 을 취 하 는 방법: 키 워드 를 취 하 는 것 은 산열 표 의 길이 보다 크 지 않 은 숫자 P 에 의 해 제 거 된 후에 얻 은 나머지 는 산열 주소 이다.예 를 들 어 키워드 200, P = 30;나머지 20 은 키워드 200 의 해시 주소 이다.          3. 나머지 를 제외 한 방법 으로 간단 한 Hash 구 조 를 실현 합 니 다.  똑똑 한 당신 은 나머지 를 제외 하고 같은 해시 주 소 를 가 진 상황 이 발생 할 수 있다 고 생각 할 것 입 니 다.  이 문 제 를 처리 하기 위해 서 우 리 는 배열 과 링크 를 공동으로 사용 해 야 한다.  그 중에서 배열 은 링크 를 저장 하고 링크 는 요 소 를 저장 합 니 다.  남아 있 는 방법 으로 요소 의 색인 을 얻 습 니 다. 같은 해시 주소 가 있 으 면 이 데 이 터 를 이 위치 링크 에 추가 합 니 다.
  그러면 우 리 는 먼저 노드 클래스 를 정의 합 니 다.
  package hashV3;

public class DataNode {
	public int member;
	public DataNode next;
}

 링크 를 정의 하고 데이터 추가 와 삭 제 를 실현 합 니 다.

package hashV3;

public class MyHash {
	private DataNode[] array = new DataNode[100];
	
	private int getHash(DataNode node){
		int index = node.member%10;
		return index;
	}
	
	/**
	 *     
	 * @param node
	 */
	public void add(DataNode node){
		int index = this.getHash(node);
		if(array[index] == null){
			array[index] = node;
		}else{
			node.next = array[index];
			array[index] = node;
			System.out.println("====--->>>>"+node.member);
		}
		
	}
	
	public boolean remove(DataNode node){
		int index = this.getHash(node);
		if(node == null || array[index]==null){ //         
			return false;
		}
		
		DataNode temp = array[index];
		if(temp.member==node.member){//           
			array[index] = temp.next;
		}
		
		while(temp.next.member != node.member && temp.next!=null){
			temp = temp.next;
		}
		temp.next = temp.next.next;
		return true;
	}
	
	/**
	 *     
	 */
	public void print(){
		for(int i=0; i<array.length; i++){
			if(array[i]!= null){
				DataNode node = array[i];
				while(node != null){
					System.out.println("        "+node.member);
					node = node.next;
				}
			}
		}
	}
}

  주 함수 에서 데이터 추가 와 삭 제 를 실현 합 니 다.

package hashV3;

import java.util.Random;
	
public class HashMain {
	public static void main(String[] args){
		HashMain h = new HashMain();
		h.add();
	    h.remove();
	}
	
	/**
	 *     
	 */
	private void add(){
		MyHash hash = new MyHash();
		Random rand = new Random();
		for(int i=0; i<10; i++){
			int a = rand.nextInt(4);
			DataNode node = new DataNode();
			node.member = a;
			hash.add(node);
		}
		hash.print();
	}
	
	/**
	 *     
	 */
	private void remove(){
		MyHash hash = new MyHash();
		DataNode n = new DataNode();
		n.member = 2;
		hash.remove(n);
		System.out.println("************************************************");
		hash.print();
	}
}