简单模拟一下HashMap的实现

• hashMap的实现是由数组和链表，数据结构是"链表散列"

1.准备数据 实体类Info

package com.gwzan.map;

/**
 * 员工信息类
 * @author zan
 *
 */
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;
	}
	
	
}

 2.结点

package com.gwzan.map;

/**
 * 链接点 ，相当于是车厢
 * @author zan
 *
 */
public class Node {

	public Info info;  //数据域
    public Node next;  //指针域
    
    public Node(Info info){
    	this.info=info;
    }
    
}

 3.链表

package com.gwzan.map;
/**
 * 链表，相当于火车
 * @author zan
 *
 */
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 tmp=first;
		first=tmp.next;
		return tmp;
	}
	
    
    /**
     * 查找方法
     */
    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;
    }
}

 

4.hashmap类

 

package com.gwzan.map;

import java.math.BigInteger;


/**
 * 哈希表——链地址法:
 * 哈希表每个单元设置链表，某个数据项的关键字还是像通常一样映射到哈希表的单元中，
 * 而数据项本身是插入到单元的链表中
 * @author zan
 *
 */
public class HashMap {

	private LinkList[] arr;
	
	public HashMap(){
		arr=new LinkList[100];
	}
	
	public HashMap(int maxsize){
		arr=new LinkList[maxsize];
	}
	
	/**
	 * 插入数据
	 * @param info
	 */
	public void insert(Info info){
		//获得关键字
		String key=info.getKey();
		//关键字所自定的哈希数
		int hashVal=hashCode(key);
		
		if (arr[hashVal]==null) {
			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;
	}
	
	//解决哈希冲突的
	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();
	}
}

 

5.测试类

package com.gwzan.map;

public class TestHashMap {

	public static void main(String[] args) {
		//HashMap hashMap=new HashMap(10000);
		HashMap hashMap=new HashMap();
		hashMap.insert(new Info("a", "张三"));
		hashMap.insert(new Info("ct", "李四"));
		hashMap.insert(new Info("b", "王五"));
		
		
		System.out.println(hashMap.find("a").getName());
		System.out.println(hashMap.find("ct").getName());
		System.out.println(hashMap.find("b").getName());
		
		
		System.out.println(hashMap.hashCode("a"));
		System.out.println(hashMap.hashCode("ct"));
		
		System.out.println(hashMap.delete("b").getName());
		//System.out.println(hashMap.find("b").getName());
	}
}