Java基础-1-从Hash到HashMap

2022/4/18 11:42:37

编程Tag： hash value key Java 链表 int hashmap

本文主要是介绍Java基础-1-从Hash到HashMap，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

目录
  • hash是什么
  • hash值如何计算
  • Hash碰撞(冲突)
  • HashMap
    • 1. HashMap初始化数组大小的计算
    • 2. 计算值存放的数组索引
    • 3. HashMap扩容
    • 4. HashMap解决Hash冲突时使用的链表和红黑树
    • 5. 为什么一定要重写equals和hashCode方法

hash是什么

Java中hash可以认为是唯一编码、摘要值，不同对象的计算方式不同。实质上将任意长度的输入，通过散列算法，变成固定长度的输出，输出值便是hash(散列)值。

hash值如何计算

  1. Object类的hash值为经过处理的JVM虚拟机中分配的内存地址，这样就可以区分出不同的对象，要比较对象中的值是否相等来判断当前对象是否相等，就需要重写对象的equals方法来判断。
    /** java.lang.Object **/
/** This is typically implemented by converting the internal
    address of the object into an integer **/
public native int hashCode();
  2. String类的hash值是根据算法计算字符串内容，但是并不能保证不同的字符串内容hash值不一样，真正要比较内容时，需要使用equals方法逐字符比较。
    /** The value is used for character storage. */
private final char value[];

/** Cache the hash code for the string **/
private int hash; // Default to 0

public int hashCode() {
    // 此hash为字符串刚创建时初始化值为0的值
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;
        // 基本方法就是用现有的hash值乘以31，再加上当前字符的unicode值(十进制)
        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        // 计算完毕以后给字符串设置计算后的hash值用来缓存
        hash = h;
    }
    return h;
}
  3. Integer类的hash值是包含整数的数值。
    private final int value;

public int hashCode() {
    return Integer.hashCode(value);
}

public static int hashCode(int value) {
    return value;
}

Hash碰撞(冲突)

  • 因为Hash的特性，导致了有可能造成不同的输入会生成相同的散列值，这就产生了Hash碰撞。
  • 如何解决：
    1. 开放定址法：再散列法，将产生冲突的hash值再次hash计算，依次进行，知道找到不冲突的hash地址。
    2. 再hash法：同时构造多个不同的hash函数，当计算出来的hash地址产生冲突时，计算下一个，知道冲突不再产生。
    3. 链地址法：将所有hash地址相同的元素狗造成一个成为同义词链的单链表，将头指针记录在哈西表的单元中，在HashMap中使用。
    4. 建立公共溢出区：将hash表分为基本表和溢出表，和基本表发生冲突的一律填入溢出表。

HashMap

HashMap是使用到Hash，也是面试中被提问到最多的一种，其实现的原理就是散列+数据。因为存储的数据是键值对，根据计算键的散列值计算出值应该存放的下标，从而实现查找效率为O(1)。

1. HashMap初始化数组大小的计算

  • 如果创建时HashMap的默认初始化大小为16，这是应该是设计者的经验之为。
  • 如果初始化时，给HashMap添加了初始容量大小，则会计算出比传入值大的离着最近的2n + 1的值作为初始容量，见下：
    /** java.util.HashMap **/
// 最大容量，值为正整数二进制30位为1的，十进制是1073741824
static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认载荷系数
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 带参构造器
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

// 带参构造器，只保留关键业务代码
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity > MAXIMUM_CAPACITY) {
        initialCapacity = MAXIMUM_CAPACITY;
    }
    tableSizeFor(initialCapacity);
}

// 计算比传入值更大的最接近的2^n + 1的值作为HashMap初始数组大小
static final int tableSizeFor(int cap) {
    // 以防传入的值正好是2^n值
    int n = cap - 1;
    // 以下操作是将传入值二进制位中从左到右第一个1及后续位全部置1来求得极限2^n值
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    // 如果极限值超过了2^30 + 1(也就是1 << 30)，则用最大值，如果小于，则加1凑够1*10^n
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
  • 这里会涉及到一个为什么使用2n + 1方式进行初始化大小问题，原因请见下方HashMap扩容。

2. 计算值存放的数组索引

  1. 计算key的hash值
    使用循环每一个字符执行 31 * hash + 字符的十进制UTF-16码值，得出来的hash值
  2. 充分散列
    充分散列值的计算是基于hash值的基础上进行充分散列实现的，因为key的hash值是int类型的，将高16位和低16位进行位异或操作。这样既可以不太过复杂导致影响性能，又可以做到充分散列，这样产生的散列值便具有高位和低位的性质所以才满足充分散列的要求，减少哈希碰撞，充分使用列表中的每一块内存。
    /** java.util.HashMap **/
// 充分散列
static final int hash(Object key) {
    int h;
    // 计算出key的hash值(如上)，然后将二进制hash值的高16位进行无符号向右移动16位，之后这两个int类型的值做异或操作
    // 其次这里的.hashCode()，如果是个私有对象的话，需要重写hashCode()和equals()方法，否则会取到对象的虚拟内存地址，下面有讲
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
  3. 计算HashMap中维护列表索引
    计算索引值从数学逻辑上来讲，就是使用散列值除以列表的长度取得的余数，不过因为散列值会非常的大，这样计算会非常消耗资源，由于列表的长度是2n + 1，那么只要计算2n及以内的数值作为下标即可，这样就可以对2n和散列值使用位与，这样得到的值肯定就在2n及以内，故推算出效率更高的计算方式 n % hash(key) == (n - 1) & hash(key)。
    /** java.util.HashMap **/
// 内部维护的列表
transient Node<K, V>[] table;

// .put(key, value)方法(只取部分代码)
final V putVal(int hash, K key, V value, ...) {
    // 缓存HashMap中的列表
    Node<K, V>[] tab;
    // 缓存目标列表下标的对象
    Node<K, V> p;
    // 计算后列表的长度和目标索引值
    int n, i;
    // 判断内部列表是否为空或者长度为0，满足任一进行扩容(扩容方法在下面)，并缓存内部列表到tab，缓存列表长度到n。注意：如果HashMap只初始化而未填充时，填充第一个键值时table==null，会进入这里，同时重新计算临界值threshold。
    if ((tab = table) == null || (n = tab.length) == 0) {
        n = (tab = resize()).length;
    }
    // 计算目标索引值，并判断在列表中是否已有使用，如果没有使用直接把key和value放进去，如果有了则需要解决Hash冲突
    if ((p = tab[i = (n - 1) & hash]) == null) {
        tab[i] = newNode(hash, key, value, null);
    } else {
        // 当前列表索引的位置不为null，检查当前key和put的key是否相等，相等则做更新操作。
        // 不相等的话需要检查这个值是什么类型的，如果是红黑树，则做树的插入或者更新；如果不是那就是链表，遍历链表是否有key一致的值，有则更新，无则新增，新增的时候需要检查是否超过8个，超过8个就需要构建红黑树(Java 8后支持)。
        // 这里面还有个问题，就是在判断key是否一致的时候，使用的是.hash方法和.equals方法，如果key的类型是私有对象，没有重写equals和hashCode方法就会造成永远无法对相同的对象进行更新或者获取(因为获取的是Object的hashCode方法，即虚拟内存地址)，这样大量的put会造成内存泄露，最后导致内存溢出(OOM)。
        // K k;
        // if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
    }
}

3. HashMap扩容

  1. 为什么要扩容（是不是有点智障的问题）
    • HashMap中维护着一个table(列表)、size(当前容量)、threshold(临界值)和默认值为0.75的loadFactor(载荷系数)。一个HashMap实际的最大容量(threshold)实际上是根据 table.length(当前列表的长度) * 设置的载荷系数计算而出。
    • 这个0.75的载荷系数是在利用率和碰撞几率中较优的设定，更大的系数虽然利用率提高了，但是可能会增大碰撞几率导致存储读取效率降低；更小的系数虽然降低了碰撞几率，但是会造成内存的浪费，而且在扩容时需要重新计算每个键的hash值并重新放入列表中。
    • 在put方法中，最后计算size值的时候，和临界值进行的对比，如果大于临界值，则进行扩容。
      // put()->putVal，摘取部分代码
final V putVal(int hash, K key, V value, ...) {
    // more code...
    if (++size > threshold) {
        resize();
    }
}
  2. resize()方法
    resize方法就是对HashMap进行扩容的方法，主要是初始化table(第一次put时)、计算临界值(第一次put时根据初始化值 * 载荷系数得出，以后扩大临界值，直接使用 << 1，就相当于随着table一起扩大了)、table中数据重新计算索引然后冲新添到列表中。
    // 只摘取部分方法
final Node<K,V>[] resize() {
    // 缓存列表
    Node<K,V>[] oldTab = table;
    // 缓存旧列表容量
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 缓存旧临界值
    int oldThr = threshold;
    // 初始化新列表容量和临界值
    int newCap, newThr = 0;
    if (oldCap > 0) {
        // 如果原数组就大于等于最大限制，就不允许扩容了
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 后续扩容时计算新数组大小和临界值，只需要将二进制位向前推一下即可（在保证int不溢出的时候）
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // 只有赋初始值的第一次put的时候才会走到这里，因为初始化时计算的临界值其实是列表的最大长度而不是真的临界值
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    // 完全没有赋初始值的第一次put走这里，用的是默认大小列表长度16和临界值12
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 赋初始值的第一次put会计算临界值的具体数值，后续扩容在上方
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                (int)ft : Integer.MAX_VALUE);
    }
    // 重新给临界值赋予正确的数值
    threshold = newThr;
    // 下面就是给列表扩容后重新计算hash值重新规划
  3. 为什么列表容量大小是2n + 1，扩容也要乘2呢
    • 首先因为计算键索引的公式是：(列表长度 - 1) & hash，这样做的好处是效率高、离散度高碰撞率低、空间利用率高，算出来的直接就是索引值。
    • 列表长度-1正好是2n，二进制中每一位都是1，和hash按位与出来的结果，不同数据不容易产生碰撞，例如：
      // 列表长度为16时，与数值8和9分别按位与
1000 & 1111 = 1000
1001 & 1111 = 1001
// 列表长度为15时，与数值8和9分别按位与，则会产生碰撞
1000 & 1110 = 1000
1001 & 1110 = 1000
    • 因为最后一位永远是0，造成0001、0011、0101、1001、1011、0111、1101这几个索引无法存放数据，造成极大浪费。
    • 正因为如此，在多方面考虑下，选用了2n + 1来作为列表长度，正因如此，所以扩容的时候需要保证这个比例，就要以2的倍数来扩容。

4. HashMap解决Hash冲突时使用的链表和红黑树

  1. 产生冲突如何处理
    当HashMap的键产生Hash冲突时，一般使用链表来保存冲突的数据，不过这样查改的效率就会降低到O(n)，因为链表需要从头到位依次查询，因为效率降低，所以Java8中，将单条超过链表长度阈值(8)且HashMap中数据个数大于等于64的链表转换为红黑树，这样查改效率就可以提升到\(O(log_2n)\)。但是因为红黑树的一个节点相当于链表两个节点的大小，导致不会在一开始就使用红黑树。
    // 链表切换树的最大长度
static final int TREEIFY_THRESHOLD = 8;
// 链表切换树最小列表长度
static final int MIN_TREEIFY_CAPACITY = 64;

// 摘取部分代码
final V putVal(int hash, K key, V value, ...) {
    // 这部分代码是table为空扩容和目标索引为null时操作，见上面计算索引代码
    // more...
    // 初始化一个"指针"e和key值
    Node<K,V> e; K k;
    // 这部分代码是更新操作和目标是红黑树时操作
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
        e = p;
    else if (p instanceof TreeNode)
        // 红黑树更新或添加成功后会返回null
        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    // 这里是链表操作
    else {
        // 遍历链表p的时候统计着有多少个
        for (int binCount = 0; ; ++binCount) {
            // 因为p是链表对象，所以要遍历p，e就是链表的下一个，如果下一个为空，则将数据填充进去
            if ((e = p.next) == null) {
                p.next = newNode(hash, key, value, null);
                // 如果当前链表的个数大于或者等于TREEIFY_THRESHOLD（因为从0开始，所以要减1）
                if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                    // 链表转为树
                    treeifyBin(tab, hash);
                break;
            }
            // 如果遍历的以后发现链表中的key和put的key相同，那就是更新操作
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                break;
            // 如果不想等也不为null的时候，因为e指向下一个，那么p就需要等于e，然后再次循环的时候，e就指向下下个
            p = e;
        }
    }
    // 如果找到了需要填充的地方，把新值填充进去就可以了，除了TreeNode
    if (e != null) { // existing mapping for key
        V oldValue = e.value;
        if (!onlyIfAbsent || oldValue == null)
            e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
}

// 链表转树也有条件的，必须列表长度大于64的时候，否则就是扩容列表（精简代码）
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
}
  2. 红黑树
    主要涉及到二叉查找树和2-3查找树，详见大红本
    1. 满足条件
      • 红链接均为左链接
      • 没有任何一个节点同时和两条红链接相连
      • 树为完美黑色平衡，即任意空链接到根结点的路径上黑链接数量相同
    2. 优点
      • 将红链接画平，空链接到根结点距离相同；红链接合并，就得到一个平衡的2-3查找树。所以红黑树就是将二叉查找树中简洁高效的查找方法和2-3树中搞笑的平衡插入算法相结合
    3. 红链接标识：指向当前节点的链接是红色的，当前节点就标识为red。
    4. 旋转
      如果遇到红色右链接或者两条连续红链接，则需要进行旋转。
      1. 左旋转是将右链接转到左边，将链接向父节点的当前节点的指针移动到右子树，然后将当前节点作为右子树的左子树，然后当前节点的右子树承接原右子树的左子节点。
      2. 右旋转就是左旋转相反的操作。
    5. 插入节点
      每次插入一个节点，就需要标记新增节点为red。正是因为新增的节点是red，就可能产生红色右链接或者连续红链接，此时就需要通过旋转和颜色转换来实现平衡。
    6. 颜色转换
      当节点的左右节点都是红链接，就需要将此两红链接转为黑链接，然后将节点链接的父节点置红。如果是根节点连接了两红链接，那么转换的时候，树的高度会加一（因为树的根节点总是黑色的）。
    7. 总结：
      • 如果右子节点是红色，左子节点是黑色，进行左旋转。
      • 如果左子节点是红色，且它的左子节点也是红色，则进行右旋转。
      • 如果左右子节点都是红色，进行颜色转换，高度+1。
  3. 链表转树
    无需赘述，就是一个LinkedList。
  4. 树转链表
    当树的节点少于等于6的时候，会将树重新转化为链表。

5. 为什么一定要重写equals和hashCode方法

  1. hashCode方法主要用于将entity放入HashMap、HashSet等框架中，放入时校验规律为：
    • 两对象相等，hashCode一定相等；hashCode相等，但对象不一定相等。
    • 两对象不等，hashCode不一定不等；hashCode不等，两对象一定不等。
  2. 不重写equals方法，两个对象相等比较的就是虚拟内存地址；不重写hashCode方法，计算出来的就是对象的虚拟内存地址的hashCode。这对于HashMap和HashSet中存放、修改、读取数据是否准确来说是至关重要的。不重写，数据就可能无法读取、修改和错误的存放。导致内存泄露以至于内存溢出产生OOM问题。
  3. HashMap中如何使用到
    • put方法：先对key获取hashCode索引值，然后根据索引找到Entry对象，然后使用equals对key值进行对比，对比成功再写入或更新value值。
    • get方法：和put方法一样，只不过最后的写入操作变为读取value操作。
  4. 注
    • 一般使用的HashMap和HashSet方法，都会以字符串或者数值的形式来作为key值，此时因为这两种都有官方的方法进行重写equals和hashCode，不用担心会出问题。最主要的是以自定义对象作为key值的场景时需要注意重写这两个方法，否则获取的都是内存地址，无法正常使用！


这篇关于Java基础-1-从Hash到HashMap的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！


相关编程文章

更多>
本站官方QQ
官方QQ:
23002807

沪ICP备2023033072号-1

     

扫一扫关注最新编程教程