HashMap源码讲解一 hash算法

叁歲伎倆 2022-09-12 01:54 177阅读 0赞

## **1 什么是hash算法** ##

**  来自百度百科**

**  **Hash算法可以将一个数据转换为一个标志，这个标志和源数据的每一个字节都有十分紧密的关系。Hash算法还具有一个特点，就是很难找到逆向规律

** 个人批语**

通过hash算法可以把一个数据转换为一个值，这个值暂用很小的空间，但是这个转换是不可逆的

## **2 Java中hash算法的应用**          ##

java 的 根对象 Object 存在 hashCode方法，是native修饰

/**
         * Returns a hash code value for the object. This method is
         * supported for the benefit of hash tables such as those provided by
         * {@link java.util.HashMap}.
         * <p>
         * The general contract of {@code hashCode} is:
         * <ul>
         * <li>Whenever it is invoked on the same object more than once during
         *     an execution of a Java application, the {@code hashCode} method
         *     must consistently return the same integer, provided no information
         *     used in {@code equals} comparisons on the object is modified.
         *     This integer need not remain consistent from one execution of an
         *     application to another execution of the same application.
         * <li>If two objects are equal according to the {@code equals(Object)}
         *     method, then calling the {@code hashCode} method on each of
         *     the two objects must produce the same integer result.
         * <li>It is <em>not</em> required that if two objects are unequal
         *     according to the {@link java.lang.Object#equals(java.lang.Object)}
         *     method, then calling the {@code hashCode} method on each of the
         *     two objects must produce distinct integer results.  However, the
         *     programmer should be aware that producing distinct integer results
         *     for unequal objects may improve the performance of hash tables.
         * </ul>
         * <p>
         * As much as is reasonably practical, the hashCode method defined by
         * class {@code Object} does return distinct integers for distinct
         * objects. (This is typically implemented by converting the internal
         * address of the object into an integer, but this implementation
         * technique is not required by the
         * Java™ programming language.)
         *
         * @return  a hash code value for this object.
         * @see     java.lang.Object#equals(java.lang.Object)
         * @see     java.lang.System#identityHashCode
         */
        public native int hashCode();

** 个人批语**

**             **自己新建的对象需要重新这个方法，不然得到的hascode值相同

得到的hash值都是int类型

##   **3 hash算法在 HashMap中的应用** ##

HashMap 是Key Value的存储形式，从大方向的讲解 Key的存储结构是可以独立来说的

** Key的数据结构**

数组

/* ---------------- Fields -------------- */
    
        /**
         * The table, initialized on first use, and resized as
         * necessary. When allocated, length is always a power of two.
         * (We also tolerate length zero in some operations to allow
         * bootstrapping mechanics that are currently not needed.)
         */
        transient Node<K,V>[] table;

**问题反思**

数组的存储是根据索引进行的，那么如何确定一个key应该在数组何处索引位置

数组是定长的,那么扩容的时候应该如何处理呢

** Key如何确定索引位置   **

**            **首先把Key取hash,得到一个int类型的hashcode

/**
         * Computes key.hashCode() and spreads (XORs) higher bits of hash
         * to lower.  Because the table uses power-of-two masking, sets of
         * hashes that vary only in bits above the current mask will
         * always collide. (Among known examples are sets of Float keys
         * holding consecutive whole numbers in small tables.)  So we
         * apply a transform that spreads the impact of higher bits
         * downward. There is a tradeoff between speed, utility, and
         * quality of bit-spreading. Because many common sets of hashes
         * are already reasonably distributed (so don't benefit from
         * spreading), and because we use trees to handle large sets of
         * collisions in bins, we just XOR some shifted bits in the
         * cheapest possible way to reduce systematic lossage, as well as
         * to incorporate impact of the highest bits that would otherwise
         * never be used in index calculations because of table bounds.
         */
        static final int hash(Object key) {
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }

计算key对应的下标值

i = (n - 1) & hash

**从源码中可以借鉴的思想**

**    **hash算法的应用可以解决kafka消费有序性的问题

&比直接使用取模效率高的场景