배열 과 링크 로 hashmap 사용자 정의

데이터 구 조 를 처음 배 울 때 여러분 들 은 항상 hash 함수 에 대한 이해 가 투철 하지 않 고 우수한 저장 구조 라 는 것 만 알 고 그 이 유 를 모 릅 니 다. 최근 에 hash 함수 의 원 리 를 깊이 알 고 많은 것 을 얻 었 습 니 다. 그러면 hash 함수 가 어떻게 생 겨 났 는 지 개인 적 인 이 해 를 말씀 드 리 겠 습 니 다.
배열 을 응용 할 때 우 리 는 배열 이 이러한 특성 을 가지 고 있다 는 것 을 알 게 될 것 이다.
1. 찾기 가 편리 하고 아래 표 시 를 통 해 직접 찾 을 수 있 으 며 속도 가 빠 르 고 효율 이 높다.
2. 요 소 를 추가 하고 삭제 할 때 배열 을 새로 만들어 야 합 니 다. 시간 과 공간 에서 의 대가 가 매우 큽 니 다.
배열 에 존재 하 는 단점 을 고려 하여 우 리 는 자 연 스 럽 게 다른 데이터 구조 인 링크 를 연상 시 킬 것 이다. 링크 는 다음 과 같은 특징 이 있다.
1. 링크 는 하나의 노드 로 연결 되 어 있 기 때문에 요 소 를 삭제 하고 증가 할 때 지 정 된 위치 와 전후의 두 노드 만 바 꾸 면 효율 이 높다.
2. 링크 를 찾 을 때 링크 를 옮 겨 다 니 며 시간 대가 가 크다.
상기 두 가지 데이터 구조 에 모두 단점 이 존재 하 는 것 을 감안 하여 배열 처럼 편리 하 게 찾 을 수 있 고 링크 처럼 효율 적 인 저장 과 삭제 가 가능 하 다 면 문 제 는 쉽게 해결 된다. 이로써 우 리 는 Hashmap 이라는 데이터 구 조 를 도입 했다. 이 는 체인 표 와 배열 의 결합 체 로 이해 할 수 있 고 우 리 는 배열 과 링크 를 이용 하여 hash 구 조 를 사용자 정의 할 수 있다.절 차 는 다음 과 같다.
1. 적당 한 길이 의 배열 만 들 기;
2. 하나의 결점 류 를 정의 하고 그 안에 저장 할 정보의 속성 과 다음 결점 을 가리 키 는 '지침' 을 봉 한다.
3. 데 이 터 를 추가 할 때마다 새로운 노드 의 번호 속성 에 따라 이 속성 에 대해 모델 링 (예 를 들 어 num% arr. length) 을 하고 모델 링 을 한 후에 숫자 를 얻 으 며 이 새로운 노드 에 대응 하 는 배열 좌표 입 니 다.만약 배열 에서 이 좌표 가 대응 하 는 위치 에 하나의 노드 나 하나의 노드 체인 이 있다 면 새 배열 을 끝까지 추가 합 니 다.
    4. 배열 의 특정한 아래 에 표 시 된 링크 의 길이 가 규정된 값 에 이 르 면 밸브 값) 배열 하 다. 
 
 
 
 

package netjava.cn;
/**
 *    
 * @author Administrator
 *
 */
public class Node {
	
	private int num;
	private String name;
	private String pwd;
	private Node next;
	
	public Node(int num,String name,String pwd){
		this.num = num;
		this.name = name;
		this.pwd = pwd;
	}
	public void setNext(Node next){
		this.next = next;
	}
	public Node getNext(){
		return this.next;
	}
	public int getNum() {
		return num;
	}
	public String getName() {
		return name;
	}
	public String getPwd() {
		return pwd;
	}
	@Override
	public String toString() {
		// TODO Auto-generated method stub
		return "  ："+num+">  ："+name+">  ："+pwd;
	}
}

 

package netjava.cn;
/**
 *       
 * @author Administrator
 *
 */
public class Combine {

	public Combine(Node node) {
		this.node = node;
	}
    
	//     
	private Node node;
    //    
	private int length = 1;
	
	/**          */
    public Node lastNode(){
    	Node n = node;
    	while(n.getNext() != null){
    		n = n.getNext();
    	}
    	return n;
    }
    
   /**           */
    public void printNode(){
    	Node n = node;
    	System.out.println(n);
    	while(n.getNext() != null){
    		n = n.getNext();
    		System.out.println(n);
    	}
    }
    /**       */
    public int addLength(){
    	return length++;
    }
    
    
    /*     */
	public Node getNode() {
		return node;
	}
	
	public int getLength() {
		return length;
	}
	public void setLength(int length) {
		this.length = length;
	}
}

 

package netjava.cn;

import java.util.Random;

public class DefineHash {

	private int length = 10;
	private int limit = 10;
	private Combine[] arr = new Combine[length];//         

	public static void main(String[] args) {
		DefineHash hash = new DefineHash();
		Combine[] arr = hash.buildArr();
		hash.print(arr);
		Node n0 = new Node(23, "   ", "  @！！");
		hash.add(n0);
		Node n1= new Node(24, "   ", "  @！！");
		hash.add(n1);
		for (int i = 0; i < 100; i++) {
			Node n = new Node(25+i, "   ", "  @！！");
			hash.add(n);
		}
	}

	/**       */
	public Combine[] buildArr() {

		//        length   
		arr = new Combine[length];
		//     50        
		Random random = new Random();
		for (int i = 0; i < 4; i++) {
			//     num
			int next = random.nextInt(50);
			//     
			Node node = new Node(next, "poppy", "12345678");
			//   num  ，        
			int index = next % length;
			// index       
			if (arr[index] != null) {
				Combine com = arr[index];
				//       +1
				com.addLength();
				//        
				Node pre = com.lastNode();
				pre.setNext(node);
			} else { // index      ，    
				arr[index] = new Combine(node);
			}
		}
		return arr;
	}

	/**      */
	public Combine[] add(Node node) {
		//     
		int num = node.getNum();
		//   num  ，        
		int index = num % length;
		// index       ，       
		if (arr[index] != null) {
			Combine com = arr[index];
			//          
			if (com.getLength() < limit) {
				System.out.println("   ");
				Node pre = com.lastNode();
				pre.setNext(node);
				com.addLength();
			} else { //         ，    
				System.out.println("  ");
				Combine[] c = reSort(arr);
				arr =c;
			}
		} else { // index      ，    
			arr[index] = new Combine(node);
		}
		return arr;
	}

	/**      */
	public void delete(Node node) {

	}

	/**      */
	public void find(Node node) {

	}

	/**      */
	public Combine[] reSort(Combine[] arr) {
		System.out.println("    !!!");
		length *= 2;//        2 
		limit *= 2;//      2 
		Combine[] larr = new Combine[length];
		//     ，       
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] != null) {
				Combine combine = arr[i];
				//       
				Node n = combine.getNode();
				int num = n.getNum();
				int index = num % length;
				//    index    
				if(larr[index] != null){
					Combine com = larr[index];
					com.addLength();//  +1
					com.lastNode().setNext(n);
				}else{//    Index    
					larr[index] = combine;
				}
				
			}
		}
		this.print(larr);
		System.out.println("last");
		System.out.println(larr.length+"     ");
		return larr;
	}

	/**   hash  */
	public void print(Combine[] arr) {
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] != null) {
				System.out.println(i + ">>>>>");
				arr[i].printNode();

			}
		}
	}
}