JDK源码阅读——模拟HashMap

曾经终败给现在 2022-07-12 07:00 228阅读 0赞

阅读过JDK源码,发现其实HashMap的实现就是一张散列表,由数组和链表组成,下面可以用简单的代码去模拟一下hashMap的插入和获取过程

package yyf.java.util.Map.model;
    
    /**
     * Map的模拟
     * 
     * @author yuyufeng
     *
     * @param <K>
     * @param <V>
     */
    public class MyMap<K, V> {
    	/**
    	 * 当length = 2^n时，不同的hash值发生碰撞的概率比较小，这样就会使得数据在table数组中分布较均匀，查询速度也较快
    	 * （扩容时其中的indexFor -> h & (length-1)) 这里就不做处理，模拟时只做%length
    	 */
    	static final int ARRAYMAX = 16;
    
    	/**
    	 * 构造函数初始化数组
    	 */
    	public MyMap() {
    		table = new Node[ARRAYMAX];
    	}
    
    	/**
    	 * 数组
    	 */
    	Node<K, V>[] table;
    
    	/**
    	 * 获取key的hash值
    	 * 
    	 * @param key
    	 * @return
    	 */
    	static final int hash(Object key) {
    		int h;
    		return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    	}
    
    	/**
    	 * 根据key获取value
    	 * 
    	 * @param key
    	 * @return
    	 */
    	public V get(Object key) {
    		int index = hash(key) % ARRAYMAX;
    		Node<K, V> p = table[index];
    		while (p != null) {
    			if (p.key.equals(key)) {
    				break;
    			}
    			p = p.next;
    		}
    		if (p == null) {
    			return null;
    		}
    		return p.value;
    	}
    
    	/**
    	 * put key-vlaue
    	 * 
    	 * @param key
    	 * @param value
    	 */
    	public void put(K key, V value) {
    		Node<K, V> p, q;
    		// 计算key需要存放的在table数组中的位置
    		int index = hash(key) % ARRAYMAX;
    		// 每个table都挂上node，node的如何均匀分布、如何效率这里不做要求
    		if (table[index] == null) {
    			table[index] = new Node(hash(key), key, value, null);
    		} else {
    			q = table[index];
    			// p = q.next;
    			p = q;
    			boolean flag = true;
    			while (p != null) {
    				// 如果已经存在，则覆盖
    				if (key.equals(p.key)) {
    					flag = false;
    					p.value = value;
    					break;
    				}
    				q = p;
    				p = p.next;
    			}
    
    			if (flag) {
    				p = new Node(hash(key), key, value, null);
    				q.next = p;
    			}
    
    		}
    	}
    
    	/**
    	 * 打印所有key-value
    	 */
    	public void printKVs() {
    		Node<K, V> p;
    		for (int i = 0; i < ARRAYMAX; i++) {
    			p = table[i];
    			System.out.println("[table] " + i + " ->");
    			while (p != null) {
    				System.out.println(p.key + " " + p.value);
    				p = p.next;
    			}
    		}
    	}
    
    	/**
    	 * 删除key-value
    	 * 
    	 * @param key
    	 * @return
    	 */
    	public V remove(Object key) {
    		int index = hash(key) % ARRAYMAX;
    		Node<K, V> p = table[index];
    		Node<K, V> q;
    		q = p;
    		while (p != null) {
    			if (p.key.equals(key)) {
    				q.next = p.next;
    				break;
    			}
    			q = p;
    			p = p.next;
    		}
    		if (p == null) {
    			return null;
    		}
    		return p.value;
    	}
    
    }
    
    class Node<K, V> {
    	int hash;
    	K key;
    	V value;
    	Node<K, V> next;
    
    	public Node() {
    
    	}
    
    	public Node(int hash, K key, V value, Node<K, V> next) {
    		this.hash = hash;
    		this.key = key;
    		this.value = value;
    		this.next = next;
    	}
    
    }

test.java

package yyf.java.util.Map.model;
    
    public class Test {
    
    	public static void main(String[] args) {
    		MyMap<String, String> map = new MyMap<>();
    		map.put("k1", "v1");
    		map.put("k11", "v11");
    		map.put("k2", "v2");
    		map.put("k22", "v22");
    		map.put("k3", "v3");
    		map.put("k33", "v33");
    		map.put("k23", "v23");
    		map.put("k4", "v4");
    		map.put("k41", "v41");
    		map.put("k5", "value5");
    		map.put("kabc", "vabc");
    		map.put("k4", "v5");// 塞入相同的key，则覆盖
    		System.out.println("删除k22: "+map.remove("k22"));
    		map.printKVs();
    
    		System.out.println("##获取key：k4 " + map.get("k4"));
    		System.out.println("##获取key：k6 " + map.get("k6"));
    
    		// System.out.println(hash("dasd"));
    
    	}
    
    	static final int hash(Object key) {
    		int h;
    		return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    	}
    
    }

console

删除k22: v22
    [table] 0 ->
    [table] 1 ->
    [table] 2 ->
    [table] 3 ->
    [table] 4 ->
    [table] 5 ->
    kabc vabc
    [table] 6 ->
    k1 v1
    [table] 7 ->
    k2 v2
    [table] 8 ->
    k3 v3
    [table] 9 ->
    k4 v5
    k41 v41
    [table] 10 ->
    k11 v11
    k33 v33
    k5 value5
    [table] 11 ->
    [table] 12 ->
    [table] 13 ->
    k23 v23
    [table] 14 ->
    [table] 15 ->
    ##获取key：k4 v5
    ##获取key：k6 null