>> 欢迎您 客人: 登录 | 注册 | 在线 | 搜索 | 风格 | 帮助 | 统计 | 文章 返回首页
>>分享Java编程技术，对《Java面向对象编程》等书籍提供技术支持 书籍支持  卫琴直播  品书摘要  在线测试  资源下载  联系我们
Java技术网站 → 『 Java开发技术 』 → 『 Java编程技术专题 』 → HashMap中 get 和 put 操作的具体过程
发表一个新主题 开启一个新投票 回复文章 您是本文章第 20581 个阅读者 刷新本主题
 * 贴子主题:  HashMap中 get 和 put 操作的具体过程 回复文章 点赞(0)  收藏  
作者:flybird    发表时间：2020-03-31 19:52:34     消息  查看  搜索  好友  邮件  复制  引用
  

说在前面

本文包含手写泛型HashMap<K,V>为简化版，仅为理解 HashMap 的 get() 和put() 方法的工作过程，非Java源码。

get(K key) 原理

  1. 先计算出key对应的hash值

    int hash = key.hashCode();
    //此处的 hashCode() 方法为 Object对象 所属方法，默认都有
    //自定义的类需要覆写该方法

  2. 对超出数组范围的hash值进行处理

    hash = (hash >>> 16)^hash;//java内部自做的优化，为了使hash值更加均衡，减少冲突
    int index = hash & (table.length - 1);//对下标进行合理化，以免下标越界
    //这样做可以使index在数组长度范围内的原因或者一个前提是，这里的数组的长度一定是2的n次方，
    //这样table.length - 1 在二进制情况下，除最高位，其余低位为一定是1，用hash与这样的一个数进行与操作
    //即只保留了hash的二进制的低位，就会使hash的范围一定小于数组长度

  3. 根据正确的hash值（下标值）找到所在的链表的头结点

    Entry<K,V> node = table[index];

  4. 遍历链表，如果key值相等，返回对应的value值,否则返回null
while(node != null){
    if(node.key.equals(key)){
        return node.value;
    }
    node = node.next;
}

  • 具体实现 get(K key)

@Override
    public V get(K key) {
        int hash = key.hashCode();
        hash = (hash >>> 16)^hash;//java内部自做的优化，为了使hash值更加均衡
        int index = hash & (table.length - 1);
        Entry<K,V> node = table[index];
        while(node != null){
            if(node.key.equals(key)){
                return node.value;
            }
            node = node.next;
        }
        return null;
    }

put(K key,V value) 原理

  1. 先计算出key对应的hash值
  2. 对超出数组范围的hash值进行处理
  3. 根据正确的hash值（下标值）找到所在的链表的头结点
  4. 如果头结点==null，直接将新结点赋值给数组的该位置

    Entry<K,V> newNode = new Entry<>(key,value);
    table[index] = newNode;

  5. 否则，遍历链表，找到key相等的节点，并进行value值的替换，返回旧的value值

    Entry<K,V> pre = null;//用来追踪该段链表的最后一个结点，为尾插做准备，如果采用头插法，则不需要
    while(node != null){
    if(node.key.equals(key)){
        V oldValue = node.value;
        node.value = value;
        return oldValue;
    }
    pre = node;
    node = node.next;
    }

  6. 如果没有找到，采用尾插法（1.8）/头插法（1.7）创建新结点并插入到链表中

    pre.next = new Entry<>(key,value);

  7. 将存储元素数量+1  !!!
  8. 校验是否需要扩容(需要全部重新计算hash值，因为数组长度改变了)
    1）扩容原因：为了减少hash冲突，降低冲突率（插入一个新的key时，会遇到冲突的概率）
    2）负载因子=所有key的数量 / 数组的长度
    3）冲突率和负载因子成正相关！因此为了降低冲突率，可改变数组的长度！
    4）具体操作：通过计算负载因子并与扩容因子（规定为0.75）进行比较

    if((double) size / table.length >= 0.75 ){
        resize();
    }

private void resize(){
    /**
    * 1.创造新数组，长度为原数组的2倍
    * 2.遍历原数组，找到每一条链表的头节点
    * 3.遍历每一条链表，新建结点并将节点采用头插法插入到新数组中
    *
    */
    Entry<K,V>[] newTable = new Entry;
    for(int i = 0; i < table.length; i++){
        Entry<K,V> node = table[i];
        while(node != null){
            Entry<K,V> newNode = new Entry<>(node.key,node.value);
            int hash = node.key.hashCode();
            hash = (hash >>> 16) ^ hash;
            int index = hash ^ (newTable.length - 1);
            //使用头插，尾插也可以
            newNode.next = newTable[index];
            newTable[index] = newNode;
            node = node.next;
        }
    }
}

  • 具体实现 put(K key,V value)

@Override
public V put(K key, V value) {
    int hash = key.hashCode();
    hash = (hash >>> 16)^hash;//java内部自做的优化语句，为了使hash值更加均衡
    int index = hash & (table.length - 1);
    Entry<K,V> node = table[index];
    if(node == null){
        Entry<K,V> newNode = new Entry<>(key,value);
        table[index] = newNode;
    }else{
        Entry<K,V> pre = null;
        while(node != null){
            if(node.key.equals(key)){
                V oldValue = node.value;
                node.value = value;
                return oldValue;
            }
            pre = node;
            node = node.next;
        }
        pre.next = new Entry<>(key,value);
    }
    size++;
    if((double) size / table.length >= LOAD_FACTOR_THRESHOLD ){
        resize();
    }
    return null;
}

具体实现HashMap<K,V>

package advance_ds.hashmap;
//接口
public interface Map<K,V> {
    V get(K key);

    V put(K key,V value);

}

/**
* @author Maria
* @program JavaDaily
* @date 2020/3/21 14:51
*/
public class HashMap<K,V> implements Map<K,V> {
    //链表的节点类
    private static class Entry<K,V>{
        K key;
        V value;
        Entry<K,V> next;

        public Entry(K key,V value){
            this.key = key;
            this.value = value;
        }
    }

    //基本存储方式：数组
    private Entry<K,V>[] table = new Entry[16];
    //存储的元素的个数
    private int size = 0;
    //扩容因子
    private static final double LOAD_FACTOR_THRESHOLD = 0.75;

    @Override
    public V get(K key) {
        /**
         * 1.先计算出key对应的hash值
         * 2.对超出数组范围的hash值进行处理
         * 3.根据正确的hash值（下标值）找到所在的链表的头结点
         * 4.遍历链表，如果key值相等，返回对应的value值,否则返回null
         */
        int hash = key.hashCode();
        hash = (hash >>> 16)^hash;//java内部自做的优化，为了使hash值更加均衡
        int index = hash & (table.length - 1);
        Entry<K,V> node = table[index];
        while(node != null){
            if(node.key.equals(key)){
                return node.value;
            }
            node = node.next;
        }
        return null;
    }

    @Override
    public V put(K key, V value) {
        /**
         * 1.先计算出key对应的hash值
         * 2.对超出数组范围的hash值进行处理
         * 3.根据正确的hash值（下标值）找到所在的链表的头结点
         * 4.如果头结点==null，直接将新结点赋值给数组的该位置
         * 5.否则，遍历链表，找到key相等的节点，并进行value值的替换，返回旧的value值
         * 6.如果没有找到，采用尾插法（1.8）/头插法（1.7）创建新结点并插入到链表中
         * 7.将存储元素数量+1
         * 8.校验是否需要扩容(需要全部重新计算hash值，因为数组长度改变了)
         *      扩容原因：为了减少hash冲突，冲突率：插入一个新的key时，会遇到冲突的概率
         *          负载因子=所有key的数量/数组的长度
         *          冲突率和负载因子成正相关！因此为了降低冲突率，可改变数组的长度！
         *      具体操作：通过计算负载因子并与扩容因子进行比较
         */

        int hash = key.hashCode();
        hash = (hash >>> 16)^hash;//java内部自做的优化语句，为了使hash值更加均衡
        int index = hash & (table.length - 1);
        Entry<K,V> node = table[index];
        if(node == null){
            Entry<K,V> newNode = new Entry<>(key,value);
            table[index] = newNode;
        }else{
            Entry<K,V> pre = null;
            while(node != null){
                if(node.key.equals(key)){
                    V oldValue = node.value;
                    node.value = value;
                    return oldValue;
                }
                pre = node;
                node = node.next;
            }
            pre.next = new Entry<>(key,value);
        }
        size++;
        if((double) size / table.length >= LOAD_FACTOR_THRESHOLD ){
            resize();
        }
        return null;

    }

    private void resize(){
        /**
         * 1.创造新数组，长度为原数组的2倍
         * 2.遍历原数组，找到每一条链表的头节点
         * 3.遍历每一条链表，新建结点并将节点采用头插法插入到新数组中
         *
        */
        Entry<K,V>[] newTable = new Entry;
        for(int i = 0; i < table.length; i++){
            Entry<K,V> node = table[i];
            while(node != null){
                Entry<K,V> newNode = new Entry<>(node.key,node.value);
                int hash = node.key.hashCode();
                hash = (hash >>> 16) ^ hash;
                int index = hash ^ (newTable.length - 1);
                //使用头插，尾插也可以
                newNode.next = newTable[index];
                newTable[index] = newNode;
                node = node.next;
            }
        }
    }
}

写一个类来测试一下这段代码

package advance_ds.hashmap;

import java.util.Objects;

/**
* @author Maria
* @program JavaDaily
* @date 2020/3/21 21:29
*/
public class Person {
    private String name;
    private int age;
    private int gender;

    //自动生成的
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return age == person.age &&
                Objects.equals(name, person.name) &&
                Objects.equals(gender, person.gender);
    }
    //自动生成的
    @Override
    public int hashCode() {
        return Objects.hash(name, age, gender);
    }

    public static void main(String[] args) {
        Person p1 = new Person();
        p1.name = "p1";
        p1.age = 18;
        p1.gender = 0;
        Person p2 = new Person();
        p2.name = "p1";
        p2.age = 18;
        p2.gender = 0;
        HashMap<Person,Integer> map = new HashMap<>();
        map.put(p1,108);
        System.out.println(map.get(p2));//结果为108，成功取出！因为key对应的hash相等
    }
}

----------------------------
原文链接:https://blog.51cto.com/14233363/2480832

程序猿的技术大观园：www.javathinker.net



[这个贴子最后由 flybird 在 2020-04-08 09:50:04 重新编辑]
Java精品书籍推荐
Java最新视频教程推荐
  Java面向对象编程-->内部类
  JavaWeb开发-->JSP技术详解（Ⅰ）
  JSP与Hibernate开发-->通过JPA API检索数据
  Java网络编程-->通过JDBC API访问数据库
  精通Spring-->Vue Router路由管理器
  Vue3开发-->Vue简介
本站其他相关文章
  [分享]遊藝場開分員會很難嗎？原來工作項目是這些！
  孙卫琴的视频课程的源代码下载
  Java设计模式: 里氏替换原则和合成复用原则详解
  Java设计模式：接口隔离原则和迪米特法则详解
  Java中保留数字的若干位小数位数的方法
  Java的对象的拷贝方式集合
  BST 二叉搜索树
  Java设计模式：装饰器模式
  Socket服务器的整体架构
  redis持久化问题处理
  Java Scoket之java.io.EOFException解决方案
  Java入门实用代码：修改链表LinkedList
  JAVA设计模式之备忘录模式原理与用法详解
  正则表达式【匹配非字母和数字】
  初学者该学哪种编程语言
  更多...
 IPIP: 已设置保密
树形列表:   
你也許聽過或是看過眾多娛樂城的廣告，例如WM百家樂、... kericnnoe 2023-03-07 00:28:07
共1页 1条记录 当前第1页
发表一个新主题 开启一个新投票 回复文章

中文版权所有： JavaThinker技术网站 Copyright 2016-2026 沪ICP备16029593号-2
荟萃Java程序员智慧的结晶，分享交流Java前沿技术。  联系我们
如有技术文章涉及侵权，请与本站管理员联系。