手动写一个简易HashMap,慢慢完善

我就是我 2024-02-18 15:06 32阅读 0赞

**暂且只有存值和取值的功能,没有null值判断...没有实现自动扩容..待完善,以此**

public class MyHashMap<K,V> {
    
    
    /**
    * 定义一个内部类来存储键值对,即存储节点
    * @author Shinelon
    *
    * @param <K>
    * @param <V>
    */
    static class Entry<K,V>{
    /**
     * 这里注意,final不能修饰使用前未初始化的值,
     * final修饰的引用,指向的地址将不能改变(地址中的值是可以改变的,如果过可以的话),
     * 所以不初始化如果是用默认值初始化值将没有意义.
     * 可以在构造方法中进行初始化值,如果加上空参构造将会报错.
     */
    final K key;
    V value;
    int hash;//哈希值,用来?
    Entry<K,V> next;//下一个节点地址
    //满参构造
    public Entry(K key, V value, int hash, Entry<K, V> next) {
    super();
    this.key = key;
    this.value = value;
    this.hash = hash;
    this.next = next;
    }
    }
    /**
     * 定义一个方法通过key值获取哈希值
     */
    transient int hashSeed=0;//初始化一个哈希值(transient:不被序列化标记)
    public int hash(Object k){
    int h=hashSeed;
    //如果k是String类型且不是0,则调用工具类返回哈希值sun.misc.Hashing.stringHash32((String) k);
    if(0!=hashSeed&&k instanceof String){
    return sun.misc.Hashing.stringHash32((String)k);
    }
    //获得k的地址值异或运算
    h ^= k.hashCode();
    //一系列位运算
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
    }
     
     
    /**
     * 这是真正的存储容器
     * 定义一个存储节点的数组,大小16
     */
    Entry[] table=new Entry[16];
     
    /**
     * 定义一个存储数据的方法,如果是新增就返回null,如果是覆盖,就返回旧值
     * @param key
     * @param value
     * @return
     */
    public V put(K key,V value){
    //根据键获取哈希值
    int hash = hash(key);
    //获取哈希值对应的数组节点索引(即应该存放的数组的索引位置)&||运算(换成2进制,有都是1就是1|只要有1就是1)
    int i = hash & (table.length-1);
    //获得数组节点对象
    Entry<K,V> entry =  table[i];
    /**
    * 遍历以entry对象开头的链表,判断K值是否已经存在
    */
    for (Entry<K,V> entryfor=entry;entryfor!=null ; entryfor=entryfor.next) {
    //K值占用的情况(哈希值相同,且地址值相同或是对象相同)
    if(entryfor.hash==hash&&(entryfor==entry)||entryfor.equals(entry)){
    V oldValue = entryfor.value;//将旧值存储起来,以便于返回
    entryfor.value=value;
    return oldValue;
    }
    }
    /**
    * 存入键值对
    *  modCount++;源码中有,目的是抛出并发修改异常(如果没有,则抛出的是索引越界异常)
    */
    addEntry(hash,key,value,i);
    return null;
    }
    /**
     * 判断是否需要扩容
     */
    public void addEntry(int hash,K key,V value,int i){
    //判断扩容
     
    //存入
    createEntry(hash,key,value, i);
    }
    /**
     * 将需要存入的Entry对象替换原数组索引上的节点Entry对象
     */
    public void createEntry(int hash,K key,V value,int i){
    //取出数组索引上的节点对象(旧)
    Entry<K,V> entry = table[i];
    //将旧节点对象存入新节点对象中
    Entry<K, V> newEntry = new Entry<>(key, value, hash, entry);
    //将新节点对象存入数组索引位置上.
    table[i]=newEntry;
    }
     
     
    /**
     * 取值的方法get
     */
    public V get(K key){
    //根据key获取哈希值
    int hash = hash(key);
    //获取table数组索引
    int i =hash &(table.length-1);
    //获取节点Entry对象
    Entry<K,V> entry = table[i];
    //遍历以entry为头的链表
    for (Entry<K,V> entry1=entry; entry1!=null; entry1=entry1.next) {
    if(entry1.hash==hash&&(entry1.key==key||entry1.equals(key))){
    return entry1.value;
    }
    }
    return null;
    }
    }