欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

简单模拟一下HashMap的实现

程序员文章站 2022-05-21 15:17:13
...
  • 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());
	}
}

 

相关标签: HashMap java