精华内容
下载资源
问答
  • 一、什么是哈希表 讨论哈希表之前,我们先大概了解下其他数据结构...对于一般的插入删除操作,涉及到数组元素的移动,其平均复杂度也为O(n) 线性链表 对于链表的新增,删除等操作(找到指定操作位置后),仅需

    一、什么是哈希表

    在讨论哈希表之前,我们先大概了解下其他数据结构在新增,查找等基础操作执行性能

    • 数组
      采用一段连续的存储单元来存储数据。对于指定下标的查找,时间复杂度为O(1);
      通过给定值进行查找,需要遍历数组,逐一比对给定关键字和数组元素,时间复杂度为O(n),当然,对于有序数组,则可采用二分查找,插值查找,斐波那契查找等方式,可将查找复杂度提高为O(logn);
      对于一般的插入删除操作,涉及到数组元素的移动,其平均复杂度也为O(n)
    • 线性链表
      对于链表的新增,删除等操作(在找到指定操作位置后),仅需处理结点间的引用即可,时间复杂度为O(1),而查找操作需要遍历链表逐一进行比对,复杂度为O(n)
    • 二叉树
      对一棵相对平衡的有序二叉树,对其进行插入,查找,删除等操作,平均复杂度均为O(logn)。
    • 哈希表
      相比上述几种数据结构,在哈希表中进行添加,删除,查找等操作,性能十分之高,不考虑哈希冲突的情况下,仅需一次定位即可完成,时间复杂度为O(1).

    哈希表上面的特性,哈希表的主干就是数组。

    img

    哈希表

    比如我们要新增或查找某个元素,我们通过把当前元素的关键字 通过某个函数映射到数组中的某个位置,通过数组下标一次定位就可完成操作。
    存储位置 = f(关键字)
    其中,这个函数f一般称为哈希函数,这个函数的设计好坏会直接影响到哈希表的优劣。
    查找操作同理,先通过哈希函数计算出实际存储地址,然后从数组中对应地址取出即可。

    二、哈希冲突

    通过哈希函数得出的实际存储地址相同怎么办?也就是说,当我们对某个元素进行哈希运算,得到一个存储地址,然后要进行插入的时候,发现已经被其他元素占用了,其实这就是所谓的哈希冲突,也叫哈希碰撞。

    哈希函数的设计至关重要,好的哈希函数会尽可能地保证 计算简单和散列地址分布均匀,但是不可能设计出一个绝对完美的哈希函数,我们需要清楚的是,数组是一块连续的固定长度的内存空间,再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。

    哈希冲突的解决方案有多种:开放定址法(发生冲突,继续寻找下一块未被占用的存储地址),再散列函数法,链地址法.
    HashMap即是采用了链地址法.

    • JDK7 使用了数组+链表的方式
    • JDK8 使用了数组+链表+红黑树的方式

    三、HashMap的实现原理

    HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元,每一个Entry包含一个key-value键值对。

    transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
    

    Entry是HashMap中的一个静态内部类。

    static class Entry<K,V> implements Map.Entry<K,V> {
            final K key;
            V value;
            Entry<K,V> next;//存储指向下一个Entry的引用,单链表结构
            int hash;//对key的hashcode值进行hash运算后得到的值,存储在Entry,避免重复计算
    
            /**
             * Creates new entry.
             */
            Entry(int h, K k, V v, Entry<K,V> n) {
                value = v;
                next = n;
                key = k;
                hash = h;
            }
    

    HashMap的整体结构如下:

    img

    HashMap的结构

    • 解决冲突的链表的长度影响到HashMap查询的效率
      简单来说,HashMap由数组+链表组成的,数组是HashMap的主体,链表则是主要为了解决哈希冲突而存在的,如果定位到的数组位置不含链表(当前entry的next指向null),那么对于查找,添加等操作很快,仅需一次寻址即可;如果定位到的数组包含链表,对于添加操作,其时间复杂度为O(n),首先遍历链表,存在即覆盖,否则新增;对于查找操作来讲,仍需遍历链表,然后通过key对象的equals方法逐一比对查找。所以,性能考虑,HashMap中的链表出现越少,性能才会越好。
    • 发生冲突关于entry节点插入链表还是链头呢?
      JDK7:插入链表的头部,头插法
      JDK8:插入链表的尾部,尾插法

    JDK7

    public V put(K key, V value) {
            if (key == null)
                return putForNullKey(value);
            int hash = hash(key.hashCode());
            int i = indexFor(hash, table.length);
            for (Entry<K,V> e = table[i]; e != null; e = e.next) {
                Object k;
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
    
            modCount++;
            addEntry(hash, key, value, i);
            return null;
        }
    

    阅读源码发现,如果遍历链表都没法发现相应的key值的话,则会调用addEntry方法在链表添加一个Entry,重点就在与addEntry方法是如何插入链表的,addEntry方法源码如下:

     void addEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
            table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
            if (size++ >= threshold)
                resize(2 * table.length);
        }
    

    这里构造了一个新的Entry对象(构造方法的最后一个参数传入了当前的Entry链表),然后直接用这个新的Entry对象取代了旧的Entry链表,看一下Entry的构造方法可以知道是头插法。

    Entry( int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
    }
    

    从构造方法中的next=n可以看出确实是把原本的链表直接链在了新建的Entry对象的后边,可以断定是插入头部。

    JDK8
    还是继续查看put方法的源码查看插入节点的代码:

    //e是p的下一个节点
    if ((e = p.next) == null) {
       //插入链表的尾部
       p.next = newNode(hash, key, value, null);
       //如果插入后链表长度大于8则转化为红黑树
       if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
           treeifyBin(tab, hash);
       break;
    }
    

    从这段代码中可以很显然地看出当到达链表尾部(即p是链表的最后一个节点)时,e被赋为null,会进入这个分支代码,然后会用newNode方法建立一个新的节点插入尾部。

    四、HashMap的默认参数理解

    1.为什么HashMap的Entry数组长度默认为16呢?为什么数组长度一定要是2的n次幂呢?

    查看HashMap计算hashcode的方法获取存储的位置:
    为了减少hash值的碰撞,需要实现一个尽量均匀分布的hash函数,在HashMap中通过利用key的hashcode值,来进行位运算

    img

    存储的流程

     /**
         * Returns index for hash code h.
         */
        static int indexFor(int h, int length) {
            return h & (length-1);
        }
    

    举个例子
    1.计算"book"的hashcode
    十进制 : 3029737
    二进制 : 101110001110101110 1001

    2.HashMap长度是默认的16,length - 1的结果
    十进制 : 15
    二进制 : 1111

    3.把以上两个结果做与运算
    101110001110101110 1001 & 1111 = 1001
    1001的十进制 : 9,所以 index=9

    结论:hash算法最终得到的index结果,取决于hashcode值的最后几位
    现在,我们假设HashMap的长度是10,重复刚才的运算步骤:
    hashcode : 101110001110101110 1001
    length - 1 : 1001
    index : 1001


    再换一个hashcode 101110001110101110 1111 试试:
    hashcode : 101110001110101110 1111
    length - 1 : 1001
    index : 1001
    从结果可以看出,虽然hashcode变化了,但是运算的结果都是1001,也就是说,当HashMap长度为10的时候,有些index结果的出现几率会更大而有些index结果永远不会出现(比如0111),这样就不符合hash均匀分布的原则
    反观长度16或者其他2的幂,length - 1的值是所有二进制位全为1,这种情况下,index的结果等同于hashcode后几位的值,只要输入的hashcode本身分布均匀,hash算法的结果就是均匀的。


    结论

    • HashMap的默认长度为16和规定数组长度为2的幂,是为了降低hash碰撞的几率。

    2.HashMap扩容限制的负载因子为什么是0.75呢?为什么不能是0.1或者1呢?

    由HashMap的put方法中实现中的addEntry的实现代码可知当数组长度达到限制条件的阈值就要进行数组的扩容。
    扩容的方式是:
    新建一个长度为之前数组2倍的新的数组,然后将当前的Entry数组中的元素全部传输过去,扩容后的新数组长度为之前的2倍,所以扩容相对来说是个耗资源的操作。
    扩容的触发条件:
    阈值 = 数组默认的长度 x 负载因子(阈值=16x0.75=12)

    threshold = (int)(capacity * loadFactor);
    
    void addEntry(int hash, K key, V value, int bucketIndex) {
            if ((size >= threshold) && (null != table[bucketIndex])) {
                resize(2 * table.length);//当size超过临界阈值threshold,并且即将发生哈希冲突时进行扩容
                hash = (null != key) ? hash(key) : 0;
                bucketIndex = indexFor(hash, table.length);
            }
    
            createEntry(hash, key, value, bucketIndex);
        }
    

    由上面的内容可知,

    • 如果负载因子为0.5甚至更低的可能的话,最后得到的临时阈值明显会很小,这样的情况就会造成分配的内存的浪费,存在多余的没用的内存空间,也不满足了哈希表均匀分布的情况。
    • 如果负载因子达到了1的情况,也就是Entry数组存满了才发生扩容,这样会出现大量的哈希冲突的情况,出现链表过长,因此造成get查询数据的效率。
    • 因此选择了0.5~1的折中数也就是0.75,均衡解决了上面出现的情况。

    五、JDK8下的HashMap的实现

    区别:

    • 使用一个Node数组取代了JDK7的Entry数组来存储数据,这个Node可能是链表结构,也可能是红黑树结构;

    • 如果插入的元素key的hashcode值相同,那么这些key也会被定位到Node数组的同一个格子里,如果不超过8个使用链表存储;

    • 超过8个,会调用treeifyBin函数,将链表转换为红黑树。那么即使所有key的hashcode完全相同,由于红黑树的特点,查找某个特定元素,也只需要O(logn)的开销。

      img

      JDK8的HashMap

    上图是示意图,主要是描述结构,不会达到这个状态的,因为这么多数据的时候早就扩容了。

    put

    • 和 Java7 稍微有点不一样的地方就是,Java7 是先扩容后插入新值的,Java8 先插值再扩容,不过这个不重要。

    get

    • 计算 key 的 hash 值,根据 hash 值找到对应数组下标: hash & (length-1)
    • 判断数组该位置处的元素是否刚好就是我们要找的,如果不是,走第三步
    • 判断该元素类型是否是 TreeNode,如果是,用红黑树的方法取数据,如果不是,走第四步 遍历链表,直到找到相等(==或equals)的 key

    六、CurrentHashMap的原理

    由于HashMap是线程不同步的,虽然处理数据的效率高,但是在多线程的情况下存在着安全问题,因此设计了CurrentHashMap来解决多线程安全问题。

    HashMap在put的时候,插入的元素超过了容量(由负载因子决定)的范围就会触发扩容操作,就是rehash,这个会重新将原数组的内容重新hash到新的扩容数组中,在多线程的环境下,存在同时其他的元素也在进行put操作,如果hash值相同,可能出现同时在同一数组下用链表表示,造成闭环,导致在get时会出现死循环,所以HashMap是线程不安全的。

    JDK7下的CurrentHashMap

    在JDK1.7版本中,ConcurrentHashMap的数据结构是由一个Segment数组和多个HashEntry组成,主要实现原理是实现了锁分离的思路解决了多线程的安全问题,如下图所示:

    img

    CurrentHashMap的结构

    Segment数组的意义就是将一个大的table分割成多个小的table来进行加锁,也就是上面的提到的锁分离技术,而每一个Segment元素存储的是HashEntry数组+链表,这个和HashMap的数据存储结构一样。

    ConcurrentHashMap 与HashMap和Hashtable 最大的不同在于:put和 get 两次Hash到达指定的HashEntry,第一次hash到达Segment,第二次到达Segment里面的Entry,然后在遍历entry链表.

    初始化

    ConcurrentHashMap的初始化是会通过位与运算来初始化Segment的大小,用ssize来表示,源码如下所示

    private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
    private void writeObject(java.io.ObjectOutputStream s)
            throws java.io.IOException {
            // For serialization compatibility
            // Emulate segment calculation from previous version of this class
            int sshift = 0;
            int ssize = 1;
            while (ssize < DEFAULT_CONCURRENCY_LEVEL) {
                ++sshift;
                ssize <<= 1;
            }
            int segmentShift = 32 - sshift;
            int segmentMask = ssize - 1;
    

    因为ssize用位于运算来计算(ssize <<=1),所以Segment的大小取值都是以2的N次方,无关concurrencyLevel的取值,当然concurrencyLevel最大只能用16位的二进制来表示,即65536,换句话说,Segment的大小最多65536个,没有指定concurrencyLevel元素初始化,Segment的大小ssize默认为 DEFAULT_CONCURRENCY_LEVEL =16

    每一个Segment元素下的HashEntry的初始化也是按照位与运算来计算,用cap来表示,如下:

    int cap = 1;
    while (cap < c)
        cap <<= 1
    

    上所示,HashEntry大小的计算也是2的N次方(cap <<=1), cap的初始值为1,所以HashEntry最小的容量为2

    put操作

     static class Segment<K,V> extends ReentrantLock implements Serializable {
            private static final long serialVersionUID = 2249069246763182397L;
            final float loadFactor;
            Segment(float lf) { this.loadFactor = lf; }
        }
    

    从上Segment的继承体系可以看出,Segment实现了ReentrantLock,也就带有锁的功能,当执行put操作时,会进行第一次key的hash来定位Segment的位置,如果该Segment还没有初始化,即通过CAS操作进行赋值,然后进行第二次hash操作,找到相应的HashEntry的位置,这里会利用继承过来的锁的特性,在将数据插入指定的HashEntry位置时(链表的尾端),会通过继承ReentrantLock的tryLock()方法尝试去获取锁,如果获取成功就直接插入相应的位置,如果已经有线程获取该Segment的锁,那当前线程会以自旋的方式(如果不了解自旋锁,请参考:自旋锁原理及java自旋锁**)**去继续的调用tryLock()方法去获取锁,超过指定次数就挂起,等待唤醒.

    get

    ConcurrentHashMap的get操作跟HashMap类似,只是ConcurrentHashMap第一次需要经过一次hash定位到Segment的位置,然后再hash定位到指定的HashEntry,遍历该HashEntry下的链表进行对比,成功就返回,不成功就返回null

    size 返回ConcurrentHashMap元素大小

    计算ConcurrentHashMap的元素大小是一个有趣的问题,因为他是并发操作的,就是在你计算size的时候,他还在并发的插入数据,可能会导致你计算出来的size和你实际的size有相差(在你return size的时候,插入了多个数据),要解决这个问题,JDK1.7版本用两种方案

    try {
        for (;;) {
            if (retries++ == RETRIES_BEFORE_LOCK) {
                for (int j = 0; j < segments.length; ++j) ensureSegment(j).lock(); // force creation
            }
            sum = 0L;
            size = 0;
            overflow = false;
            for (int j = 0; j < segments.length; ++j) {
                Segment<K,V> seg = segmentAt(segments, j);
                if (seg != null) { sum += seg.modCount; int c = seg.count; if (c < 0 || (size += c) < 0)
                   overflow = true;
                } }
            if (sum == last) break;
            last = sum; } }
    finally {
        if (retries > RETRIES_BEFORE_LOCK) {
            for (int j = 0; j < segments.length; ++j)
                segmentAt(segments, j).unlock();
        }
    }
    

    1、第一种方案他会使用不加锁的模式去尝试多次计算ConcurrentHashMap的size,最多三次,比较前后两次计算的结果,结果一致就认为当前没有元素加入,计算的结果是准确的.
    2、第二种方案是如果第一种方案不符合,他就会给每个Segment加上锁,然后计算ConcurrentHashMap的size返回.

    JDK8的ConcurrentHashMap

    JDK1.8的实现已经摒弃了Segment的概念,而是直接用Node数组+链表+红黑树的数据结构来实现,并发控制使用Synchronized和CAS来操作,整个看起来就像是优化过且线程安全的HashMap,虽然在JDK1.8中还能看到Segment的数据结构,但是已经简化了属性,只是为了兼容旧版本.

    img

    JDK8的ConcurrentHashMap

    在深入JDK1.8的put和get实现之前要知道一些常量设计和数据结构,这些是构成ConcurrentHashMap实现结构的基础,下面看一下基本属性:

    // node数组最大容量:2^30=1073741824
    private static final int MAXIMUM_CAPACITY = 1 << 30;
    // 默认初始值,必须是2的幕数
    private static final int DEFAULT_CAPACITY = 16
    //数组可能最大值,需要与toArray()相关方法关联
    static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    //并发级别,遗留下来的,为兼容以前的版本
    private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
    // 负载因子
    private static final float LOAD_FACTOR = 0.75f;
    // 链表转红黑树阀值,> 8 链表转换为红黑树
    static final int TREEIFY_THRESHOLD = 8;
    //树转链表阀值,小于等于6(tranfer时,lc、hc=0两个计数器分别++记录原bin、新binTreeNode数量,<=UNTREEIFY_THRESHOLD 则untreeify(lo))
    static final int UNTREEIFY_THRESHOLD = 6;
    static final int MIN_TREEIFY_CAPACITY = 64;
    private static final int MIN_TRANSFER_STRIDE = 16;
    private static int RESIZE_STAMP_BITS = 16;
    // 2^15-1,help resize的最大线程数
    private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
    // 32-16=16,sizeCtl中记录size大小的偏移量
    private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
    // forwarding nodes的hash值
    static final int MOVED     = -1;
    // 树根节点的hash值
    static final int TREEBIN   = -2;
    // ReservationNode的hash值
    static final int RESERVED  = -3;
    // 可用处理器数量
    static final int NCPU = Runtime.getRuntime().availableProcessors();
    //存放node的数组
    transient volatile Node<K,V>[] table;
    /*控制标识符,用来控制table的初始化和扩容的操作,不同的值有不同的含义
     *当为负数时:-1代表正在初始化,-N代表有N-1个线程正在 进行扩容
     *当为0时:代表当时的table还没有被初始化
     *当为正数时:表示初始化或者下一次进行扩容的大小
    private transient volatile int sizeCtl;
    

    JDK8的Node

    Node是ConcurrentHashMap存储结构的基本单元,继承于HashMap中的Entry,用于存储数据,Node数据结构很简单,就是一个链表,但是只允许对数据进行查找,不允许进行修改
    源代码如下:

    static class Node<K,V> implements Map.Entry<K,V> {
            final int hash;
            final K key;
            volatile V val;
            volatile Node<K,V> next;
    
            Node(int hash, K key, V val, Node<K,V> next) {
                this.hash = hash;
                this.key = key;
                this.val = val;
                this.next = next;
            }
    
            public final K getKey()       { return key; }
            public final V getValue()     { return val; }
            public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
            public final String toString(){ return key + "=" + val; }
            public final V setValue(V value) {
                throw new UnsupportedOperationException();
            }
    
            public final boolean equals(Object o) {
                Object k, v, u; Map.Entry<?,?> e;
                return ((o instanceof Map.Entry) &&
                        (k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
                        (v = e.getValue()) != null &&
                        (k == key || k.equals(key)) &&
                        (v == (u = val) || v.equals(u)));
            }
    
            /**
             * Virtualized support for map.get(); overridden in subclasses.
             */
            Node<K,V> find(int h, Object k) {
                Node<K,V> e = this;
                if (k != null) {
                    do {
                        K ek;
                        if (e.hash == h &&
                            ((ek = e.key) == k || (ek != null && k.equals(ek))))
                            return e;
                    } while ((e = e.next) != null);
                }
                return null;
            }
        }
    

    TreeNode

    TreeNode继承于Node,但是数据结构换成了二叉树结构,它是红黑树的数据的存储结构,用于红黑树中存储数据,当链表的节点数大于8时会转换成红黑树的结构,他就是通过TreeNode作为存储结构代替Node来转换成黑红树源代码如下

    static final class TreeNode<K,V> extends Node<K,V> {
            TreeNode<K,V> parent;  // red-black tree links
            TreeNode<K,V> left;
            TreeNode<K,V> right;
            TreeNode<K,V> prev;    // needed to unlink next upon deletion
            boolean red;
    
            TreeNode(int hash, K key, V val, Node<K,V> next,
                     TreeNode<K,V> parent) {
                super(hash, key, val, next);
                this.parent = parent;
            }
    
            Node<K,V> find(int h, Object k) {
                return findTreeNode(h, k, null);
            }
    
            /**
             * Returns the TreeNode (or null if not found) for the given key
             * starting at given root.
             */
            final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
                if (k != null) {
                    TreeNode<K,V> p = this;
                    do  {
                        int ph, dir; K pk; TreeNode<K,V> q;
                        TreeNode<K,V> pl = p.left, pr = p.right;
                        if ((ph = p.hash) > h)
                            p = pl;
                        else if (ph < h)
                            p = pr;
                        else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
                            return p;
                        else if (pl == null)
                            p = pr;
                        else if (pr == null)
                            p = pl;
                        else if ((kc != null ||
                                  (kc = comparableClassFor(k)) != null) &&
                                 (dir = compareComparables(kc, k, pk)) != 0)
                            p = (dir < 0) ? pl : pr;
                        else if ((q = pr.findTreeNode(h, k, kc)) != null)
                            return q;
                        else
                            p = pl;
                    } while (p != null);
                }
                return null;
            }
        }
    

    TreeBin

    TreeBin从字面含义中可以理解为存储树形结构的容器,而树形结构就是指TreeNode,所以TreeBin就是封装TreeNode的容器,它提供转换黑红树的一些条件和锁的控制.

    总结和思考

    其实可以看出JDK1.8版本的ConcurrentHashMap的数据结构已经接近HashMap,相对而言,ConcurrentHashMap只是增加了同步的操作来控制并发,从JDK1.7版本的ReentrantLock+Segment+HashEntry,到JDK1.8版本中synchronized+CAS+HashEntry+红黑树,相对而言,总结如下思考

    • JDK1.8的实现降低锁的粒度,JDK1.7版本锁的粒度是基于Segment的,包含多个HashEntry,而JDK1.8锁的粒度就是HashEntry(首节点)
    • JDK1.8版本的数据结构变得更加简单,使得操作也更加清晰流畅,因为已经使用synchronized来进行同步,所以不需要分段锁的概念,也就不需要Segment这种数据结构了,由于粒度的降低,实现的复杂度也增加了
    • JDK1.8使用红黑树来优化链表,基于长度很长的链表的遍历是一个很漫长的过程,而红黑树的遍历效率是很快的,代替一定阈值的链表,这样形成一个最佳拍档
    • JDK1.8为什么使用内置锁synchronized来代替重入锁ReentrantLock,我觉得有以下几点
      1.因为粒度降低了,在相对而言的低粒度加锁方式,synchronized并不比ReentrantLock差,在粗粒度加锁中ReentrantLock可能通过Condition来控制各个低粒度的边界,更加的灵活,而在低粒度中,Condition的优势就没有了
      2.JVM的开发团队从来都没有放弃synchronized,而且基于JVM的synchronized优化空间更大,使用内嵌的关键字比使用API更加自然
      3.在大量的数据操作下,对于JVM的内存压力,基于API的ReentrantLock会开销更多的内存,虽然不是瓶颈,但是也是一个选择依据

    concurrentHashMap面试题

    1、ConcurrentHashMap有哪些构造函数?

    一共有五个,作用及代码如下:

    img

    [复制代码](javascript:void(0)😉

        //无参构造函数
        public ConcurrentHashMap() {
        }
        //可传初始容器大小的构造函数
        public ConcurrentHashMap(int initialCapacity) {
            if (initialCapacity < 0)
                throw new IllegalArgumentException();
            int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
                       MAXIMUM_CAPACITY :
                       tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
            this.sizeCtl = cap;
        }
        //可传入map的构造函数
        public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
            this.sizeCtl = DEFAULT_CAPACITY;
            putAll(m);
        }
        //可设置阈值和初始容量
        public ConcurrentHashMap(int initialCapacity, float loadFactor) {
            this(initialCapacity, loadFactor, 1);
        }
    
        //可设置初始容量和阈值和并发级别
        public ConcurrentHashMap(int initialCapacity,
                                 float loadFactor, int concurrencyLevel) {
            if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
                throw new IllegalArgumentException();
            if (initialCapacity < concurrencyLevel)   // Use at least as many bins
                initialCapacity = concurrencyLevel;   // as estimated threads
            long size = (long)(1.0 + (long)initialCapacity / loadFactor);
            int cap = (size >= (long)MAXIMUM_CAPACITY) ?
                MAXIMUM_CAPACITY : tableSizeFor((int)size);
            this.sizeCtl = cap;
        }
    

    😉

    2、ConcurrentHashMap使用什么技术来保证线程安全?

    jdk1.7:Segment+HashEntry来进行实现的;

    jdk1.8:放弃了Segment臃肿的设计,采用Node+CAS+Synchronized来保证线程安全;

    3、ConcurrentHashMap的get方法是否要加锁,为什么?

    不需要,get方法采用了unsafe方法,来保证线程安全。

    4、ConcurrentHashMap迭代器是强一致性还是弱一致性?HashMap呢?

    弱一致性,hashmap强一直性。

    ConcurrentHashMap可以支持在迭代过程中,向map添加新元素,而HashMap则抛出了ConcurrentModificationException,

    因为HashMap包含一个修改计数器,当你调用他的next()方法来获取下一个元素时,迭代器将会用到这个计数器。

    5、ConcurrentHashMap1.7和1.8的区别:

    jdk1.8的实现降低锁的粒度,jdk1.7锁的粒度是基于Segment的,包含多个HashEntry,而jdk1.8锁的粒度就是Node

    数据结构:jdk1.7 Segment+HashEntry;jdk1.8 数组+链表+红黑树+CAS+synchronized

    展开全文
  • HashMap的实现

    2020-09-14 11:06:46
    一、什么是哈希表 讨论哈希表之前,我们先大概了解下其他数据...对于一般的插入删除操作,涉及到数组元素的移动,其平均复杂度也为O(n) 线性链表:对于链表的新增,删除等操作(找到指定操作位置后),仅需处理结

    一、什么是哈希表

    在讨论哈希表之前,我们先大概了解下其他数据结构在新增,查找等基础操作执行性能

    数组:采用一段连续的存储单元来存储数据。对于指定下标的查找,时间复杂度为O(1);通过给定值进行查找,需要遍历数组,逐一比对给定关键字和数组元素,时间复杂度为O(n),当然,对于有序数组,则可采用二分查找,插值查找,斐波那契查找等方式,可将查找复杂度提高为O(logn);对于一般的插入删除操作,涉及到数组元素的移动,其平均复杂度也为O(n)

    线性链表:对于链表的新增,删除等操作(在找到指定操作位置后),仅需处理结点间的引用即可,时间复杂度为O(1),而查找操作需要遍历链表逐一进行比对,复杂度为O(n)

    二叉树:对一棵相对平衡的有序二叉树,对其进行插入,查找,删除等操作,平均复杂度均为O(logn)。

    哈希表:相比上述几种数据结构,在哈希表中进行添加,删除,查找等操作,性能十分之高,不考虑哈希冲突的情况下(后面会探讨下哈希冲突的情况),仅需一次定位即可完成,时间复杂度为O(1),接下来我们就来看看哈希表是如何实现达到惊艳的常数阶O(1)的。

    我们知道,数据结构的物理存储结构只有两种:顺序存储结构链式存储结构(像栈,队列,树,图等是从逻辑结构去抽象的,映射到内存中,也这两种物理组织形式),而在上面我们提到过,在数组中根据下标查找某个元素,一次定位就可以达到,哈希表利用了这种特性,哈希表的主干就是数组。

    比如我们要新增或查找某个元素,我们通过把当前元素的关键字 通过某个函数映射到数组中的某个位置,通过数组下标一次定位就可完成操作。
      
    这个函数可以简单描述为:存储位置 = f(关键字) ,这个函数f一般称为哈希函数,这个函数的设计好坏会直接影响到哈希表的优劣。举个例子,比如我们要在哈希表中执行插入操作:
    插入过程如下图所示
    在这里插入图片描述
    查找操作同理,先通过哈希函数计算出实际存储地址,然后从数组中对应地址取出即可。

    哈希冲突

    然而万事无完美,如果两个不同的元素,通过哈希函数得出的实际存储地址相同怎么办?也就是说,当我们对某个元素进行哈希运算,得到一个存储地址,然后要进行插入的时候,发现已经被其他元素占用了,其实这就是所谓的哈希冲突,也叫哈希碰撞。前面我们提到过,哈希函数的设计至关重要,好的哈希函数会尽可能地保证 计算简单和散列地址分布均匀,但是,我们需要清楚的是,数组是一块连续的固定长度的内存空间,再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。那么哈希冲突如何解决呢?哈希冲突的解决方案有多种:开放定址法(发生冲突,继续寻找下一块未被占用的存储地址),再散列函数法, 链地址法,而HashMap即是采用了链地址法,也就是数组+链表的方式。

    二、HashMap的实现原理

    HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元,每一个Entry包含一个key-value键值对。(其实所谓Map其实就是保存了两个对象之间的映射关系的一种集合)

    //HashMap的主干数组,可以看到就是一个Entry数组,初始值为空数组{},主干数组的长度一定是2的次幂。
    //至于为什么这么做,后面会有详细分析。
    transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
    
    

    Entry是HashMap中的一个静态内部类。代码如下

        static class Entry<K,V> implements Map.Entry<K,V> {
            final K key;
            V value;
            Entry<K,V> next;//存储指向下一个Entry的引用,单链表结构
            int hash;//对key的hashcode值进行hash运算后得到的值,存储在Entry,避免重复计算
    
            /**
             * Creates new entry.
             */
            Entry(int h, K k, V v, Entry<K,V> n) {
                value = v;
                next = n;
                key = k;
                hash = h;
            } 
    
    

    所以,HashMap的总体结构如下:
    在这里插入图片描述

    简单来说,HashMap由数组+链表组成的,数组是HashMap的主体,链表则是主要为了解决哈希冲突而存在的,如果定位到的数组位置不含链表(当前entry的next指向null),那么查找,添加等操作很快,仅需一次寻址即可;如果定位到的数组包含链表,对于添加操作,其时间复杂度为O(n),首先遍历链表,存在即覆盖,否则新增;对于查找操作来讲,仍需遍历链表,然后通过key对象的equals方法逐一比对查找。所以,性能考虑,HashMap中的链表出现越少,性能才会越好

    其他几个重要字段

    /**实际存储的key-value键值对的个数*/
    transient int size;
    
    /**阈值,当table == {}时,该值为初始容量(初始容量默认为16);当table被填充了,也就是为table分配内存空间后,
    threshold一般为 capacity*loadFactory。HashMap在进行扩容时需要参考threshold,后面会详细谈到*/
    int threshold;
    
    /**负载因子,代表了table的填充度有多少,默认是0.75
    加载因子存在的原因,还是因为减缓哈希冲突,如果初始桶为16,等到满16个元素才扩容,某些桶里可能就有不止一个元素了。
    所以加载因子默认为0.75,也就是说大小为16的HashMap,到了第13个元素,就会扩容成32。
    */
    final float loadFactor;
    
    /**HashMap被改变的次数,由于HashMap非线程安全,在对HashMap进行迭代时,
    如果期间其他线程的参与导致HashMap的结构发生变化了(比如put,remove等操作),
    需要抛出异常ConcurrentModificationException*/
    transient int modCount;
    
    

    HashMap有4个构造器,其他构造器如果用户没有传入initialCapacity 和loadFactor这两个参数,会使用默认值
    initialCapacity默认为16,loadFactory默认为0.75

    我们看下其中一个

    public HashMap(int initialCapacity, float loadFactor) {
         //此处对传入的初始容量进行校验,最大不能超过MAXIMUM_CAPACITY = 1<<30(230)
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal initial capacity: " +
                                                   initialCapacity);
            if (initialCapacity > MAXIMUM_CAPACITY)
                initialCapacity = MAXIMUM_CAPACITY;
            if (loadFactor <= 0 || Float.isNaN(loadFactor))
                throw new IllegalArgumentException("Illegal load factor: " +
                                                   loadFactor);
    
            this.loadFactor = loadFactor;
            threshold = initialCapacity;
         
            init();//init方法在HashMap中没有实际实现,不过在其子类如 linkedHashMap中就会有对应实现
        }
    
    

    从上面这段代码我们可以看出,在常规构造器中,没有为数组table分配内存空间(有一个入参为指定Map的构造器例外),而是在执行put操作的时候才真正构建table数组

    OK,接下来我们来看看put操作的实现

    public V put(K key, V value) {
            //如果table数组为空数组{},进行数组填充(为table分配实际内存空间),入参为threshold,
            //此时threshold为initialCapacity 默认是1<<4(24=16)
            if (table == EMPTY_TABLE) {
                inflateTable(threshold);
            }
           //如果key为null,存储位置为table[0]或table[0]的冲突链上
            if (key == null)
                return putForNullKey(value);
            int hash = hash(key);//对key的hashcode进一步计算,确保散列均匀
            int i = indexFor(hash, table.length);//获取在table中的实际位置
            for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            //如果该对应数据已存在,执行覆盖操作。用新value替换旧value,并返回旧value
                Object k;
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
            modCount++;//保证并发访问时,若HashMap内部结构发生变化,快速响应失败
            addEntry(hash, key, value, i);//新增一个entry
            return null;
        }
    
    

    inflateTable这个方法用于为主干数组table在内存中分配存储空间,通过roundUpToPowerOf2(toSize)可以确保capacity为大于或等于toSize的最接近toSize的二次幂,比如toSize=13,则capacity=16;to_size=16,capacity=16;to_size=17,capacity=32.

    private void inflateTable(int toSize) {
            int capacity = roundUpToPowerOf2(toSize);//capacity一定是2的次幂
            /**此处为threshold赋值,取capacity*loadFactor和MAXIMUM_CAPACITY+1的最小值,
            capaticy一定不会超过MAXIMUM_CAPACITY,除非loadFactor大于1 */
            threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
            table = new Entry[capacity];
            initHashSeedAsNeeded(capacity);
        }
    
    

    roundUpToPowerOf2中的这段处理使得数组长度一定为2的次幂,Integer.highestOneBit是用来获取最左边的bit(其他bit位为0)所代表的数值

     private static int roundUpToPowerOf2(int number) {
            // assert number >= 0 : "number must be non-negative";
            return number >= MAXIMUM_CAPACITY
                    ? MAXIMUM_CAPACITY
                    : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
        }
    
    
    

    hash函数

    /**这是一个神奇的函数,用了很多的异或,移位等运算
    对key的hashcode进一步进行计算以及二进制位的调整等来保证最终获取的存储位置尽量分布均匀*/
    final int hash(Object k) {
            int h = hashSeed;
            if (0 != h && k instanceof String) {
                return sun.misc.Hashing.stringHash32((String) k);
            }
    
            h ^= k.hashCode();
    
            h ^= (h >>> 20) ^ (h >>> 12);
            return h ^ (h >>> 7) ^ (h >>> 4);
        }
    
    

    以上hash函数计算出的值,通过indexFor进一步处理来获取实际的存储位置

    /**
         * 返回数组下标
         */
        static int indexFor(int h, int length) {
            return h & (length-1);
        }
    
    

    h&(length-1)保证获取的index一定在数组范围内,举个例子,默认容量16,length-1=15,h=18,转换成二进制计算为index=2。位运算对计算机来说,性能更高一些(HashMap中有大量位运算)

    所以最终存储位置的确定流程是这样的:
    在这里插入图片描述
    再来看看addEntry的实现:

    void addEntry(int hash, K key, V value, int bucketIndex) {
            if ((size >= threshold) && (null != table[bucketIndex])) {
                resize(2 * table.length);//当size超过临界阈值threshold,并且即将发生哈希冲突时进行扩容
                hash = (null != key) ? hash(key) : 0;
                bucketIndex = indexFor(hash, table.length);
            }
    
            createEntry(hash, key, value, bucketIndex);
        }
    
    

    通过以上代码能够得知,当发生哈希冲突并且size大于阈值的时候,需要进行数组扩容,扩容时,需要新建一个长度为之前数组2倍的新的数组,然后将当前的Entry数组中的元素全部传输过去,扩容后的新数组长度为之前的2倍,所以扩容相对来说是个耗资源的操作。

    三、为何HashMap的数组长度一定是2的次幂?

    我们来继续看上面提到的resize方法

    void resize(int newCapacity) {
            Entry[] oldTable = table;
            int oldCapacity = oldTable.length;
            if (oldCapacity == MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return;
            }
    
            Entry[] newTable = new Entry[newCapacity];
            transfer(newTable, initHashSeedAsNeeded(newCapacity));
            table = newTable;
            threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
        }
    
    

    如果数组进行扩容,数组长度发生变化,而存储位置 index = h&(length-1),index也可能会发生变化,需要重新计算index,我们先来看看transfer这个方法

    void transfer(Entry[] newTable, boolean rehash) {
            int newCapacity = newTable.length;
         //for循环中的代码,逐个遍历链表,重新计算索引位置,将老数组数据复制到新数组中去(数组不存储实际数据,所以仅仅是拷贝引用而已)
            for (Entry<K,V> e : table) {
                while(null != e) {
                    Entry<K,V> next = e.next;
                    if (rehash) {
                        e.hash = null == e.key ? 0 : hash(e.key);
                    }
                    int i = indexFor(e.hash, newCapacity);
                    //将当前entry的next链指向新的索引位置,newTable[i]有可能为空,有可能也是个entry链,如果是entry链,直接在链表头部插入。
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                }
            }
        }
    
    

    这个方法将老数组中的数据逐个链表地遍历,扔到新的扩容后的数组中,我们的数组索引位置的计算是通过 对key值的hashcode进行hash扰乱运算后,再通过和 length-1进行位运算得到最终数组索引位置。

    HashMap的数组长度一定保持2的次幂,比如16的二进制表示为 10000,那么length-1就是15,二进制为01111,同理扩容后的数组长度为32,二进制表示为100000,length-1为31,二进制表示为011111。从下图可以我们也能看到这样会保证低位全为1,而扩容后只有一位差异,也就是多出了最左位的1,这样在通过 h&(length-1)的时候,只要h对应的最左边的那一个差异位为0,就能保证得到的新的数组索引和老数组索引一致(大大减少了之前已经散列良好的老数组的数据位置重新调换),个人理解。

    在这里插入图片描述
    还有,数组长度保持2的次幂,length-1的低位都为1,会使得获得的数组索引index更加均匀

    在这里插入图片描述
    我们看到,上面的&运算,高位是不会对结果产生影响的(hash函数采用各种位运算可能也是为了使得低位更加散列),我们只关注低位bit,如果低位全部为1,那么对于h低位部分来说,任何一位的变化都会对结果产生影响,也就是说,要得到index=21这个存储位置,h的低位只有这一种组合。这也是数组长度设计为必须为2的次幂的原因。
    在这里插入图片描述
    如果不是2的次幂,也就是低位不是全为1此时,要使得index=21,h的低位部分不再具有唯一性了,哈希冲突的几率会变的更大,同时,index对应的这个bit位无论如何不会等于1了,而对应的那些数组位置也就被白白浪费了。

    get方法:

     public V get(Object key) {
         //如果key为null,则直接去table[0]处去检索即可。
            if (key == null)
                return getForNullKey();
            Entry<K,V> entry = getEntry(key);
            return null == entry ? null : entry.getValue();
     }
    
    

    get方法通过key值返回对应value,如果key为null,直接去table[0]处检索。我们再看一下getEntry这个方法

    final Entry<K,V> getEntry(Object key) {
                
            if (size == 0) {
                return null;
            }
            //通过key的hashcode值计算hash值
            int hash = (key == null) ? 0 : hash(key);
            //indexFor (hash&length-1) 获取最终数组索引,然后遍历链表,通过equals方法比对找出对应记录
            for (Entry<K,V> e = table[indexFor(hash, table.length)];
                 e != null;
                 e = e.next) {
                Object k;
                if (e.hash == hash && 
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            }
            return null;
        }    
    
    

    可以看出,get方法的实现相对简单,key(hashcode)–>hash–>indexFor–>最终索引位置,找到对应位置table[i],再查看是否有链表,遍历链表,通过key的equals方法比对查找对应的记录。要注意的是,有人觉得上面在定位到数组位置之后然后遍历链表的时候,e.hash == hash这个判断没必要,仅通过equals判断就可以。其实不然,试想一下,如果传入的key对象重写了equals方法却没有重写hashCode,而恰巧此对象定位到这个数组位置,如果仅仅用equals判断可能是相等的,但其hashCode和当前对象不一致,这种情况,根据Object的hashCode的约定,不能返回当前对象,而应该返回null,后面的例子会做出进一步解释。

    四、重写equals方法需同时重写hashCode方法

    最后我们再聊聊老生常谈的一个问题,各种资料上都会提到,“重写equals时也要同时覆盖hashcode”,我们举个小例子来看看,如果重写了equals而不重写hashcode会发生什么样的问题

    
    public class MyTest {
        private static class Person{
            int idCard;
            String name;
    
            public Person(int idCard, String name) {
                this.idCard = idCard;
                this.name = name;
            }
            @Override
            public boolean equals(Object o) {
                if (this == o) {
                    return true;
                }
                if (o == null || getClass() != o.getClass()){
                    return false;
                }
                Person person = (Person) o;
                //两个对象是否等值,通过idCard来确定
                return this.idCard == person.idCard;
            }
    
        }
        public static void main(String []args){
            HashMap<Person,String> map = new HashMap<Person, String>();
            Person person = new Person(1234,"乔峰");
            //put到hashmap中去
            map.put(person,"天龙八部");
            //get取出,从逻辑上讲应该能输出“天龙八部”
            System.out.println("结果:"+map.get(new Person(1234,"萧峰")));
        }
    }
    
    实际输出结果:null
    
    

    如果我们已经对HashMap的原理有了一定了解,这个结果就不难理解了。尽管我们在进行get和put操作的时候,使用的key从逻辑上讲是等值的(通过equals比较是相等的),但由于没有重写hashCode方法,所以put操作时,key(hashcode1)–>hash–>indexFor–>最终索引位置 ,而通过key取出value的时候 key(hashcode1)–>hash–>indexFor–>最终索引位置,由于hashcode1不等于hashcode2,导致没有定位到一个数组位置而返回逻辑上错误的值null(也有可能碰巧定位到一个数组位置,但是也会判断其entry的hash值是否相等,上面get方法中有提到。)

    所以,在重写equals的方法的时候,必须注意重写hashCode方法,同时还要保证通过equals判断相等的两个对象,调用hashCode方法要返回同样的整数值。而如果equals判断不相等的两个对象,其hashCode可以相同(只不过会发生哈希冲突,应尽量避免)。

    五、JDK1.8中HashMap的性能优化

    假如一个数组槽位上链上数据过多(即拉链过长的情况)导致性能下降该怎么办?
    JDK1.8在JDK1.7的基础上针对增加了红黑树来进行优化。即当链表超过8时,链表就转换为红黑树,利用红黑树快速增删改查的特点提高HashMap的性能,其中会用到红黑树的插入、删除、查找等算法。
    关于这方面的探讨我们以后的文章再做说明。
    附:HashMap put方法逻辑图(JDK1.8)

    在这里插入图片描述

    作者: dreamcatcher-cx
    出处: http://www.cnblogs.com/chengxiao/

    展开全文
  • Java 集合 之HashMap

    2020-07-28 17:49:52
    一、什么是哈希表 讨论哈希表之前,我们先大概了解下其他数据...对于一般的插入删除操作,涉及到数组元素的移动,其平均复杂度也为O(n) 线性链表:对于链表的新增,删除等操作(找到指定操作位置后),仅需处理结

    一、什么是哈希表

    在讨论哈希表之前,我们先大概了解下其他数据结构在新增,查找等基础操作执行性能

    数组:采用一段连续的存储单元来存储数据。对于指定下标的查找,时间复杂度为O(1);通过给定值进行查找,需要遍历数组,逐一比对给定关键字和数组元素,时间复杂度为O(n),当然,对于有序数组,则可采用二分查找,插值查找,斐波那契查找等方式,可将查找复杂度提高为O(logn);对于一般的插入删除操作,涉及到数组元素的移动,其平均复杂度也为O(n)

    线性链表:对于链表的新增,删除等操作(在找到指定操作位置后),仅需处理结点间的引用即可,时间复杂度为O(1),而查找操作需要遍历链表逐一进行比对,复杂度为O(n)

    二叉树:对一棵相对平衡的有序二叉树,对其进行插入,查找,删除等操作,平均复杂度均为O(logn)。

    哈希表:相比上述几种数据结构,在哈希表中进行添加,删除,查找等操作,性能十分之高,不考虑哈希冲突的情况下(后面会探讨下哈希冲突的情况),仅需一次定位即可完成,时间复杂度为O(1),接下来我们就来看看哈希表是如何实现达到惊艳的常数阶O(1)的。

    我们知道,数据结构的物理存储结构只有两种:顺序存储结构链式存储结构(像栈,队列,树,图等是从逻辑结构去抽象的,映射到内存中,也这两种物理组织形式),而在上面我们提到过,在数组中根据下标查找某个元素,一次定位就可以达到,哈希表利用了这种特性,哈希表的主干就是数组

    比如我们要新增或查找某个元素,我们通过把当前元素的关键字 通过某个函数映射到数组中的某个位置,通过数组下标一次定位就可完成操作。
     
    这个函数可以简单描述为:存储位置 = f(关键字) ,这个函数f一般称为哈希函数,这个函数的设计好坏会直接影响到哈希表的优劣。举个例子,比如我们要在哈希表中执行插入操作:
    插入过程如下图所示
    哈希表数据插入过程

    查找操作同理,先通过哈希函数计算出实际存储地址,然后从数组中对应地址取出即可。

    哈希冲突

    然而万事无完美,如果两个不同的元素,通过哈希函数得出的实际存储地址相同怎么办?也就是说,当我们对某个元素进行哈希运算,得到一个存储地址,然后要进行插入的时候,发现已经被其他元素占用了,其实这就是所谓的哈希冲突,也叫哈希碰撞。前面我们提到过,哈希函数的设计至关重要,好的哈希函数会尽可能地保证 计算简单和散列地址分布均匀,但是,我们需要清楚的是,数组是一块连续的固定长度的内存空间,再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。那么哈希冲突如何解决呢?哈希冲突的解决方案有多种:开放定址法(发生冲突,继续寻找下一块未被占用的存储地址),再散列函数法,链地址法,而HashMap即是采用了链地址法,也就是数组+链表的方式。

    二、HashMap的实现原理

    HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元,每一个Entry包含一个key-value键值对。(其实所谓Map其实就是保存了两个对象之间的映射关系的一种集合)

    //HashMap的主干数组,可以看到就是一个Entry数组,初始值为空数组{},主干数组的长度一定是2的次幂。
    //至于为什么这么做,后面会有详细分析。
    transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
    123
    

    Entry是HashMap中的一个静态内部类。代码如下

        static class Entry<K,V> implements Map.Entry<K,V> {
            final K key;
            V value;
            Entry<K,V> next;//存储指向下一个Entry的引用,单链表结构
            int hash;//对key的hashcode值进行hash运算后得到的值,存储在Entry,避免重复计算
    
            /**
             * Creates new entry.
             */
            Entry(int h, K k, V v, Entry<K,V> n) {
                value = v;
                next = n;
                key = k;
                hash = h;
            } 
    123456789101112131415
    

    所以,HashMap的总体结构如下:
    在这里插入图片描述

    简单来说,HashMap由数组+链表组成的,数组是HashMap的主体,链表则是主要为了解决哈希冲突而存在的,如果定位到的数组位置不含链表(当前entry的next指向null),那么查找,添加等操作很快,仅需一次寻址即可;如果定位到的数组包含链表,对于添加操作,其时间复杂度为O(n),首先遍历链表,存在即覆盖,否则新增;对于查找操作来讲,仍需遍历链表,然后通过key对象的equals方法逐一比对查找。所以,性能考虑,HashMap中的链表出现越少,性能才会越好。

    其他几个重要字段

    /**实际存储的key-value键值对的个数*/
    transient int size;
    
    /**阈值,当table == {}时,该值为初始容量(初始容量默认为16);当table被填充了,也就是为table分配内存空间后,
    threshold一般为 capacity*loadFactory。HashMap在进行扩容时需要参考threshold,后面会详细谈到*/
    int threshold;
    
    /**负载因子,代表了table的填充度有多少,默认是0.75
    加载因子存在的原因,还是因为减缓哈希冲突,如果初始桶为16,等到满16个元素才扩容,某些桶里可能就有不止一个元素了。
    所以加载因子默认为0.75,也就是说大小为16的HashMap,到了第13个元素,就会扩容成32。
    */
    final float loadFactor;
    
    /**HashMap被改变的次数,由于HashMap非线程安全,在对HashMap进行迭代时,
    如果期间其他线程的参与导致HashMap的结构发生变化了(比如put,remove等操作),
    需要抛出异常ConcurrentModificationException*/
    transient int modCount;
    1234567891011121314151617
    

    HashMap有4个构造器,其他构造器如果用户没有传入initialCapacity 和loadFactor这两个参数,会使用默认值

    initialCapacity默认为16,loadFactory默认为0.75

    我们看下其中一个

    public HashMap(int initialCapacity, float loadFactor) {
         //此处对传入的初始容量进行校验,最大不能超过MAXIMUM_CAPACITY = 1<<30(230)
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal initial capacity: " +
                                                   initialCapacity);
            if (initialCapacity > MAXIMUM_CAPACITY)
                initialCapacity = MAXIMUM_CAPACITY;
            if (loadFactor <= 0 || Float.isNaN(loadFactor))
                throw new IllegalArgumentException("Illegal load factor: " +
                                                   loadFactor);
    
            this.loadFactor = loadFactor;
            threshold = initialCapacity;
         
            init();//init方法在HashMap中没有实际实现,不过在其子类如 linkedHashMap中就会有对应实现
        }
    12345678910111213141516
    

    从上面这段代码我们可以看出,在常规构造器中,没有为数组table分配内存空间(有一个入参为指定Map的构造器例外),而是在执行put操作的时候才真正构建table数组

    OK,接下来我们来看看put操作的实现

    public V put(K key, V value) {
            //如果table数组为空数组{},进行数组填充(为table分配实际内存空间),入参为threshold,
            //此时threshold为initialCapacity 默认是1<<4(24=16)
            if (table == EMPTY_TABLE) {
                inflateTable(threshold);
            }
           //如果key为null,存储位置为table[0]或table[0]的冲突链上
            if (key == null)
                return putForNullKey(value);
            int hash = hash(key);//对key的hashcode进一步计算,确保散列均匀
            int i = indexFor(hash, table.length);//获取在table中的实际位置
            for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            //如果该对应数据已存在,执行覆盖操作。用新value替换旧value,并返回旧value
                Object k;
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
            modCount++;//保证并发访问时,若HashMap内部结构发生变化,快速响应失败
            addEntry(hash, key, value, i);//新增一个entry
            return null;
        }
    12345678910111213141516171819202122232425
    

    inflateTable这个方法用于为主干数组table在内存中分配存储空间,通过roundUpToPowerOf2(toSize)可以确保capacity为大于或等于toSize的最接近toSize的二次幂,比如toSize=13,则capacity=16;to_size=16,capacity=16;to_size=17,capacity=32.

    private void inflateTable(int toSize) {
            int capacity = roundUpToPowerOf2(toSize);//capacity一定是2的次幂
            /**此处为threshold赋值,取capacity*loadFactor和MAXIMUM_CAPACITY+1的最小值,
            capaticy一定不会超过MAXIMUM_CAPACITY,除非loadFactor大于1 */
            threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
            table = new Entry[capacity];
            initHashSeedAsNeeded(capacity);
        }
    12345678
    

    roundUpToPowerOf2中的这段处理使得数组长度一定为2的次幂,Integer.highestOneBit是用来获取最左边的bit(其他bit位为0)所代表的数值.

     private static int roundUpToPowerOf2(int number) {
            // assert number >= 0 : "number must be non-negative";
            return number >= MAXIMUM_CAPACITY
                    ? MAXIMUM_CAPACITY
                    : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
        }
    
    1234567
    

    hash函数

    /**这是一个神奇的函数,用了很多的异或,移位等运算
    对key的hashcode进一步进行计算以及二进制位的调整等来保证最终获取的存储位置尽量分布均匀*/
    final int hash(Object k) {
            int h = hashSeed;
            if (0 != h && k instanceof String) {
                return sun.misc.Hashing.stringHash32((String) k);
            }
    
            h ^= k.hashCode();
    
            h ^= (h >>> 20) ^ (h >>> 12);
            return h ^ (h >>> 7) ^ (h >>> 4);
        }
    12345678910111213
    

    以上hash函数计算出的值,通过indexFor进一步处理来获取实际的存储位置

    /**
         * 返回数组下标
         */
        static int indexFor(int h, int length) {
            return h & (length-1);
        }
    123456
    

    h&(length-1)保证获取的index一定在数组范围内,举个例子,默认容量16,length-1=15,h=18,转换成二进制计算为index=2。位运算对计算机来说,性能更高一些(HashMap中有大量位运算)

    所以最终存储位置的确定流程是这样的:
    HashMap如何确定元素位置

    再来看看addEntry的实现:

    void addEntry(int hash, K key, V value, int bucketIndex) {
            if ((size >= threshold) && (null != table[bucketIndex])) {
                resize(2 * table.length);//当size超过临界阈值threshold,并且即将发生哈希冲突时进行扩容
                hash = (null != key) ? hash(key) : 0;
                bucketIndex = indexFor(hash, table.length);
            }
    
            createEntry(hash, key, value, bucketIndex);
        }
    123456789
    

    通过以上代码能够得知,当发生哈希冲突并且size大于阈值的时候,需要进行数组扩容,扩容时,需要新建一个长度为之前数组2倍的新的数组,然后将当前的Entry数组中的元素全部传输过去,扩容后的新数组长度为之前的2倍,所以扩容相对来说是个耗资源的操作。

    三、为何HashMap的数组长度一定是2的次幂?

    我们来继续看上面提到的resize方法

    void resize(int newCapacity) {
            Entry[] oldTable = table;
            int oldCapacity = oldTable.length;
            if (oldCapacity == MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return;
            }
    
            Entry[] newTable = new Entry[newCapacity];
            transfer(newTable, initHashSeedAsNeeded(newCapacity));
            table = newTable;
            threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
        }
    12345678910111213
    

    如果数组进行扩容,数组长度发生变化,而存储位置 index = h&(length-1),index也可能会发生变化,需要重新计算index,我们先来看看transfer这个方法

    void transfer(Entry[] newTable, boolean rehash) {
            int newCapacity = newTable.length;
         //for循环中的代码,逐个遍历链表,重新计算索引位置,将老数组数据复制到新数组中去(数组不存储实际数据,所以仅仅是拷贝引用而已)
            for (Entry<K,V> e : table) {
                while(null != e) {
                    Entry<K,V> next = e.next;
                    if (rehash) {
                        e.hash = null == e.key ? 0 : hash(e.key);
                    }
                    int i = indexFor(e.hash, newCapacity);
                    //将当前entry的next链指向新的索引位置,newTable[i]有可能为空,有可能也是个entry链,如果是entry链,直接在链表头部插入。
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                }
            }
        }
    1234567891011121314151617
    

    这个方法将老数组中的数据逐个链表地遍历,扔到新的扩容后的数组中,我们的数组索引位置的计算是通过 对key值的hashcode进行hash扰乱运算后,再通过和 length-1进行位运算得到最终数组索引位置。

    HashMap的数组长度一定保持2的次幂,比如16的二进制表示为 10000,那么length-1就是15,二进制为01111,同理扩容后的数组长度为32,二进制表示为100000,length-1为31,二进制表示为011111。从下图可以我们也能看到这样会保证低位全为1,而扩容后只有一位差异,也就是多出了最左位的1,这样在通过 h&(length-1)的时候,只要h对应的最左边的那一个差异位为0,就能保证得到的新的数组索引和老数组索引一致(大大减少了之前已经散列良好的老数组的数据位置重新调换),个人理解。

    在这里插入图片描述

    还有,数组长度保持2的次幂,length-1的低位都为1,会使得获得的数组索引index更加均匀

    在这里插入图片描述
    我们看到,上面的&运算,高位是不会对结果产生影响的(hash函数采用各种位运算可能也是为了使得低位更加散列),我们只关注低位bit,如果低位全部为1,那么对于h低位部分来说,任何一位的变化都会对结果产生影响,也就是说,要得到index=21这个存储位置,h的低位只有这一种组合。这也是数组长度设计为必须为2的次幂的原因。
    在这里插入图片描述
    如果不是2的次幂,也就是低位不是全为1此时,要使得index=21,h的低位部分不再具有唯一性了,哈希冲突的几率会变的更大,同时,index对应的这个bit位无论如何不会等于1了,而对应的那些数组位置也就被白白浪费了。

    get方法

     public V get(Object key) {
         //如果key为null,则直接去table[0]处去检索即可。
            if (key == null)
                return getForNullKey();
            Entry<K,V> entry = getEntry(key);
            return null == entry ? null : entry.getValue();
     }
    1234567
    

    get方法通过key值返回对应value,如果key为null,直接去table[0]处检索。我们再看一下getEntry这个方法

    final Entry<K,V> getEntry(Object key) {
                
            if (size == 0) {
                return null;
            }
            //通过key的hashcode值计算hash值
            int hash = (key == null) ? 0 : hash(key);
            //indexFor (hash&length-1) 获取最终数组索引,然后遍历链表,通过equals方法比对找出对应记录
            for (Entry<K,V> e = table[indexFor(hash, table.length)];
                 e != null;
                 e = e.next) {
                Object k;
                if (e.hash == hash && 
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            }
            return null;
        }    
    123456789101112131415161718
    

    可以看出,get方法的实现相对简单,key(hashcode)–>hash–>indexFor–>最终索引位置,找到对应位置table[i],再查看是否有链表,遍历链表,通过key的equals方法比对查找对应的记录。要注意的是,有人觉得上面在定位到数组位置之后然后遍历链表的时候,e.hash == hash这个判断没必要,仅通过equals判断就可以。其实不然,试想一下,如果传入的key对象重写了equals方法却没有重写hashCode,而恰巧此对象定位到这个数组位置,如果仅仅用equals判断可能是相等的,但其hashCode和当前对象不一致,这种情况,根据Object的hashCode的约定,不能返回当前对象,而应该返回null,后面的例子会做出进一步解释。

    四、重写equals方法需同时重写hashCode方法

    最后我们再聊聊老生常谈的一个问题,各种资料上都会提到,“重写equals时也要同时覆盖hashcode”,我们举个小例子来看看,如果重写了equals而不重写hashcode会发生什么样的问题

    public class MyTest {
        private static class Person{
            int idCard;
            String name;
    
            public Person(int idCard, String name) {
                this.idCard = idCard;
                this.name = name;
            }
            @Override
            public boolean equals(Object o) {
                if (this == o) {
                    return true;
                }
                if (o == null || getClass() != o.getClass()){
                    return false;
                }
                Person person = (Person) o;
                //两个对象是否等值,通过idCard来确定
                return this.idCard == person.idCard;
            }
    
        }
        public static void main(String []args){
            HashMap<Person,String> map = new HashMap<Person, String>();
            Person person = new Person(1234,"乔峰");
            //put到hashmap中去
            map.put(person,"天龙八部");
            //get取出,从逻辑上讲应该能输出“天龙八部”
            System.out.println("结果:"+map.get(new Person(1234,"萧峰")));
        }
    }
    
    实际输出结果:null
    1234567891011121314151617181920212223242526272829303132333435
    

    如果我们已经对HashMap的原理有了一定了解,这个结果就不难理解了。尽管我们在进行get和put操作的时候,使用的key从逻辑上讲是等值的(通过equals比较是相等的),但由于没有重写hashCode方法,所以put操作时,key(hashcode1)–>hash–>indexFor–>最终索引位置 ,而通过key取出value的时候 key(hashcode1)–>hash–>indexFor–>最终索引位置,由于hashcode1不等于hashcode2,导致没有定位到一个数组位置而返回逻辑上错误的值null(也有可能碰巧定位到一个数组位置,但是也会判断其entry的hash值是否相等,上面get方法中有提到。)

    所以,在重写equals的方法的时候,必须注意重写hashCode方法,同时还要保证通过equals判断相等的两个对象,调用hashCode方法要返回同样的整数值。而如果equals判断不相等的两个对象,其hashCode可以相同(只不过会发生哈希冲突,应尽量避免)。
    在这里插入图片描述

    五、JDK1.8中HashMap的性能优化

    假如一个数组槽位上链上数据过多(即拉链过长的情况)导致性能下降该怎么办?
    JDK1.8在JDK1.7的基础上针对增加了红黑树来进行优化。即当链表超过8时,链表就转换为红黑树,利用红黑树快速增删改查的特点提高HashMap的性能,其中会用到红黑树的插入、删除、查找等算法。

    红黑树的英文是“Red-Black Tree",简称R-B Tree。它是一种不严格的平衡二叉查找树,我前面说了,它的定义是不严格符合平衡二叉查找树的定义的。那红黑树空间是怎么定义的呢?

    顾名思义,红黑树中的节点,一类被标记为黑色,一类被标记为红色除此之外,一棵红黑树还需要满足这样几个要求:

    • 根节点是黑色的;
    • 每个叶子节点都是黑色的空节点(NIL),也就是说,叶子节点不存储数据;
    • 任何相邻的节点都不能同时为红色,红色节点是被黑色节点隔开的;
    • 每个节点,从该节点到达其可达叶子节点的所有路径,都包含相同数目的黑色节点

    1. 红黑树概念和图示

    红黑树比较传统的定义是需要满足以下五个特征

    1. 每个节点或者是黑色,或者是红色。
    2. 根节点是黑色。
    3. 每个叶子节点(NIL)是黑色。 [注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!]
    4. 如果一个节点是红色的,则它的子节点必须是黑色的。
    5. 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

    其特点在于给数的每一个节点加上了颜色属性,在插入的过程中通过颜色变换和节点旋转调平衡。其实博主不是很喜欢上面的定义,还有一种视角就是将它与二三树比较。

    img

    2.红黑树的优势

    红黑树是”近似平衡“的

    红黑树相比avl树,在检索的时候效率其实差不多,都是通过平衡来二分查找。但对于插入删除等操作效率提高很多。红黑树不像avl树一样追求绝对的平衡,他允许局部很少的不完全平衡,这样对于效率影响不大,但省去了很多没有必要的调平衡操作,avl树调平衡有时候代价较大,所以效率不如红黑树,在现在很多地方都是底层都是红黑树的天下啦。

    红黑树的高度只比高度平衡的AVL树的高度(log2n)仅仅大了一倍,在性能上却好很多。

    HashMap在里面就是链表加上红黑树的一种结构,这样利用了链表对内存的使用率以及红黑树的高效检索,是一种很happy的数据结构。

    AVL树是一种高度平衡的二叉树,所以查找的非常高,但是,有利就有弊,AVL树为了维持这种高度的平衡,就要付出更多代价。每次插入、删除都要做调整,就比较复杂、耗时。所以,对于有频繁的插入、删除操作的数据集合,使用AVL树的代价就有点高了。

    红黑树只是做到了近似平衡,并不严格的平衡,所以在维护的成本上,要比AVL树要低。

    所以,红黑树的插入、删除、查找各种操作性能都比较稳定。对于工程应用来说,要面对各种异常情况,为了支撑这种工业级的应用,我们更倾向于这种性能稳定的平衡二叉查找树。

    3 为什么不采用AVL树

    AVL树比红黑树保持更加严格的平衡。AVL树中从根到最深叶的路径最多为~1.44 lg(n + 2),而在红黑树中最多为~2 lg(n + 1)。

    因此,在AVL树中查找通常更快,但这是以更多旋转操作导致更慢的插入和删除为代价的。因此,如果您希望查找次数主导树的更新次数,请使用AVL树。

    AVL以及RedBlack树是高度平衡的树数据结构。它们非常相似,真正的区别在于在任何添加/删除操作时完成的旋转操作次数。

    两种实现都缩放为a O(lg N),其中N是叶子的数量,但实际上AVL树在查找密集型任务上更快:利用更好的平衡,树遍历平均更短。另一方面,插入和删除方面,AVL树速度较慢:需要更高的旋转次数才能在修改时正确地重新平衡数据结构。

    对于通用实现(即先验并不清楚查找是否是操作的主要部分),RedBlack树是首选:它们更容易实现,并且在常见情况下更快 - 无论数据结构如何经常被搜索修改。一个例子,TreeMapTreeSet在Java中使用一个支持RedBlack树。

    对于小数据

    insert:RB tree&avl tree具有恒定的最大旋转次数,但RB树会更快,因为平均RB树使用较少的旋转。

    查找:AVL树更快,因为AVL树的深度较小。

    删除:RB树具有恒定的最大旋转次数,但AVL树可以将O(log N)次旋转视为最差。并且平均而言,RB树也具有较少的旋转次数,因此RB树更快。

    对于大数据

    insert:AVL树更快。因为您需要在插入之前查找特定节点。当您有更多数据时,查找特定节点的时间差异与O(log N)成比例增长。但在最坏的情况下,AVL树和RB树仍然只需要恒定的旋转次数。因此,瓶颈将成为您查找该特定节点的时间。

    查找:AVL树更快。(与小数据情况相同)

    删除:AVL树平均速度更快,但在最坏的情况下,RB树更快。因为您还需要在删除之前查找非常深的节点以进行交换(类似于插入的原因)。平均而言,两棵树都有恒定的旋转次数。但RB树有一个恒定的旋转上限。
    红黑树牺牲了一些查找性能 但其本身并不是完全平衡的二叉树。因此插入删除操作效率略高于AVL树。
    AVL树用于自平衡的计算牺牲了插入删除性能,但是因为最多只有一层的高度差,查询效率会高一些。

    **

    展开全文
  • 一、什么是哈希表 讨论哈希表之前,我们先大概了解下其他数据结构的...对于一般的插入删除操作,涉及到数组元素的移动,其平均复杂度也为O(n) 线性链表: 对于链表的新增,删除等操作(找到指定操作位置后),仅

    一、什么是哈希表

    在讨论哈希表之前,我们先大概了解下其他数据结构的新增、查找等基础操作的执行性能。

    数组:

    采用一段连续的存储单元来存储数据。对于指定下标的查找,时间复杂度为O(1);通过给定值进行查找,需要遍历数组,逐一比对给定关键字和数组元素,时间复杂度为O(n),当然,对于有序数组,则可采用二分查找,插值查找,斐波那契查找等方式,可将查找复杂度提高为O(logn);对于一般的插入删除操作,涉及到数组元素的移动,其平均复杂度也为O(n)

    线性链表:

    对于链表的新增,删除等操作(在找到指定操作位置后),仅需处理结点间的引用即可,时间复杂度为O(1),而查找操作需要遍历链表逐一进行比对,复杂度为O(n)

    二叉树:

    对一棵相对平衡的有序二叉树,对其进行插入,查找,删除等操作,平均复杂度均为O(logn)。

    哈希表:

    相比上述几种数据结构,在哈希表中进行添加,删除,查找等操作,性能十分之高,不考虑哈希冲突的情况下(后面会探讨下哈希冲突的情况),仅需一次定位即可完成,时间复杂度为O(1),接下来我们就来看看哈希表是如何实现达到惊艳的常数阶O(1)的。

    我们知道,数据结构的物理存储结构只有两种:顺序存储结构和链式存储结构(像栈,队列,树,图等是从逻辑结构去抽象的,映射到内存中,也这两种物理组织形式),而在上面我们提到过,在数组中根据下标查找某个元素,一次定位就可以达到,哈希表利用了这种特性,哈希表的主干就是数组。

    比如我们要新增或查找某个元素,我们通过把当前元素的关键字通过某个函数映射到数组中的某个位置,通过数组下标一次定位就可完成操作。
      
    这个函数可以简单描述为:存储位置 = f(关键字) ,这个函数f一般称为哈希函数,这个函数的设计好坏会直接影响到哈希表的优劣。举个例子,比如我们要在哈希表中执行插入操作:
    插入过程如下图所示:
    在这里插入图片描述
    查找操作同理,先通过哈希函数计算出实际存储地址,然后从数组中对应地址取出即可。

    哈希冲突

    然而万事无完美,如果两个不同的元素,通过哈希函数得出的实际存储地址相同怎么办?也就是说,当我们对某个元素进行哈希运算,得到一个存储地址,然后要进行插入的时候,发现已经被其他元素占用了,其实这就是所谓的哈希冲突,也叫哈希碰撞。前面我们提到过,哈希函数的设计至关重要,好的哈希函数会尽可能地保证 计算简单和散列地址分布均匀,但是,我们需要清楚的是,数组是一块连续的固定长度的内存空间,再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。那么哈希冲突如何解决呢?哈希冲突的解决方案有多种:开放定址法(发生冲突,继续寻找下一块未被占用的存储地址),再散列函数法,链地址法。而HashMap即是采用了链地址法,也就是数组+链表的方式。

    二、HashMap的实现原理

    HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元,每一个Entry包含一个key-value键值对。(其实所谓Map其实就是保存了两个对象之间的映射关系的一种集合)

    //HashMap的主干数组,可以看到就是一个Entry数组,初始值为空数组{},主干数组的长度一定是2的次幂。至于为什么这么做,后面会有详细分析。
    transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
    

    Entry是HashMap中的一个静态内部类。代码如下

        static class Entry<K,V> implements Map.Entry<K,V> {
            final K key;
            V value;
            Entry<K,V> next;//存储指向下一个Entry的引用,单链表结构
            int hash;//对key的hashcode值进行hash运算后得到的值,存储在Entry,避免重复计算
    
            /**
             * Creates new entry.
             */
            Entry(int h, K k, V v, Entry<K,V> n) {
                value = v;
                next = n;
                key = k;
                hash = h;
            } 
            
    

    所以,HashMap的总体结构如下:
    在这里插入图片描述
    简单来说,HashMap由数组+链表组成的,数组是HashMap的主体,链表则是主要为了解决哈希冲突而存在的,如果定位到的数组位置不含链表(当前entry的next指向null),那么查找,添加等操作很快,仅需一次寻址即可;如果定位到的数组包含链表,对于添加操作,其时间复杂度为O(n),首先遍历链表,存在即覆盖,否则新增;对于查找操作来讲,仍需遍历链表,然后通过key对象的equals方法逐一比对查找。所以,性能考虑,HashMap中的链表出现越少,性能才会越好

    其他几个重要字段:

    /**实际存储的key-value键值对的个数*/
    transient int size;
    
    /**阈值,当table == {}时,该值为初始容量(初始容量默认为16);
    当table被填充了,也就是为table分配内存空间后,threshold一般为 capacity*loadFactory。
    HashMap在进行扩容时需要参考threshold,后面会详细谈到*/
    int threshold;
    
    /**负载因子,代表了table的填充度有多少,默认是0.75
    加载因子存在的原因,还是因为减缓哈希冲突,如果初始桶为16,等到满16个元素才扩容,某些桶里可能就有不止一个元素了。
    所以加载因子默认为0.75,也就是说大小为16的HashMap,到了第13个元素,就会扩容成32。
    */
    final float loadFactor;
    
    /**HashMap被改变的次数,由于HashMap非线程安全,在对HashMap进行迭代时,
    如果期间其他线程的参与导致HashMap的结构发生变化了(比如put,remove等操作),
    需要抛出异常ConcurrentModificationException*/
    transient int modCount;
    

    HashMap有4个构造器,其他构造器如果用户没有传入initialCapacity 和loadFactor这两个参数,会使用默认值,initialCapacity默认值为16,loadFactory默认值为0.75

    我们看下其中一个:

    public HashMap(int initialCapacity, float loadFactor) {
         //此处对传入的初始容量进行校验,最大不能超过MAXIMUM_CAPACITY = 1<<30(230)
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal initial capacity: " +
                                                   initialCapacity);
            if (initialCapacity > MAXIMUM_CAPACITY)
                initialCapacity = MAXIMUM_CAPACITY;
            if (loadFactor <= 0 || Float.isNaN(loadFactor))
                throw new IllegalArgumentException("Illegal load factor: " +
                                                   loadFactor);
    
            this.loadFactor = loadFactor;
            threshold = initialCapacity;
         
            init();//init方法在HashMap中没有实际实现,不过在其子类如 linkedHashMap中就会有对应实现
    }
    

    从上面这段代码我们可以看出,在常规构造器中,没有为数组table分配内存空间(有一个入参为指定Map的构造器例外),而是在执行put操作的时候才真正构建table数组,我们来看看put操作的实现

    put方法

    public V put(K key, V value) {
    	 //如果table数组为空数组{},进行数组填充(为table分配实际内存空间),入参为threshold,
    	 //此时threshold为initialCapacity 默认是1<<4(2^4=16)
    	 if (table == EMPTY_TABLE) {
    	     inflateTable(threshold);
    	 }
    	//如果key为null,存储位置为table[0]或table[0]的冲突链上
    	 if (key == null)
    	     return putForNullKey(value);
    	 int hash = hash(key);//对key的hashcode进一步计算,确保散列均匀
    	 int i = indexFor(hash, table.length);//获取在table中的实际位置
    	 for (Entry<K,V> e = table[i]; e != null; e = e.next) {
    	 	 //如果该对应数据已存在,执行覆盖操作。用新value替换旧value,并返回旧value
    	     Object k;
    	     if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
    	         V oldValue = e.value;
    	         e.value = value;
    	         e.recordAccess(this);
    	         return oldValue;
    	     }
    	 }
    	 modCount++;//保证并发访问时,若HashMap内部结构发生变化,快速响应失败
    	 addEntry(hash, key, value, i);//新增一个entry
    	 return null;
    }
    
    

    inflateTable这个方法用于为主干数组table在内存中分配存储空间,通过roundUpToPowerOf2(toSize)可以确保capacity为大于或等于toSize的最接近toSize的二次幂,比如toSize=13,则capacity=16;to_size=16,capacity=16;to_size=17,capacity=32.

    private void inflateTable(int toSize) {
    	int capacity = roundUpToPowerOf2(toSize);//capacity一定是2的次幂
    	/**此处为threshold赋值,取capacity*loadFactor和MAXIMUM_CAPACITY+1的最小值,
    	capaticy一定不会超过MAXIMUM_CAPACITY,除非loadFactor大于1 */
    	threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    	table = new Entry[capacity];
    	initHashSeedAsNeeded(capacity);
    }
    

    roundUpToPowerOf2中的这段处理使得数组长度一定为2的次幂,Integer.highestOneBit是用来获取最左边的bit(其他bit位为0)所代表的数值.

    private static int roundUpToPowerOf2(int number) {
    	// assert number >= 0 : "number must be non-negative";
    	return number >= MAXIMUM_CAPACITY
    	        ? MAXIMUM_CAPACITY
    	        : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
    }
    

    hash函数:

    /**这是一个神奇的函数,用了很多的异或,移位等运算
    对key的hashcode进一步进行计算以及二进制位的调整等来保证最终获取的存储位置尽量分布均匀*/
    final int hash(Object k) {
    	int h = hashSeed;
    	if (0 != h && k instanceof String) {
    	    return sun.misc.Hashing.stringHash32((String) k);
    	}
    	
    	h ^= k.hashCode();
    	
    	h ^= (h >>> 20) ^ (h >>> 12);
    	return h ^ (h >>> 7) ^ (h >>> 4);
    }
    

    以上hash函数计算出的值,通过indexFor进一步处理来获取实际的存储位置

    /**
      * 返回数组下标
      */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }
    

    h&(length-1)保证获取的index一定在数组范围内,举个例子,默认容量16,length-1=15,h=18,转换成二进制计算为index=2(18 &15=2)。位运算对计算机来说,性能更高一些(HashMap中有大量位运算)

    所以最终存储位置的确定流程是这样的:
    在这里插入图片描述

    继续看addEntry的实现:

    void addEntry(int hash, K key, V value, int bucketIndex) {
    	if ((size >= threshold) && (null != table[bucketIndex])) {
    		resize(2 * table.length);//当size超过临界阈值threshold,并且即将发生哈希冲突时进行扩容
    		hash = (null != key) ? hash(key) : 0;
    		bucketIndex = indexFor(hash, table.length);
    	}
    	
    	createEntry(hash, key, value, bucketIndex);
    }
    

    通过以上代码能够得知,当发生哈希冲突并且size大于阈值threshold的时候,需要进行数组扩容,扩容时,需要新建一个长度为之前数组2倍的新的数组,然后将当前的Entry数组中的元素全部传输过去,扩容后的新数组长度为之前的2倍,所以扩容相对来说是个耗资源的操作。

    为什么hashMap的容量是2的幂次

    我们来继续看上面提到的resize方法:

    void resize(int newCapacity) {
    	Entry[] oldTable = table;
    	int oldCapacity = oldTable.length;
    	if (oldCapacity == MAXIMUM_CAPACITY) {
    	    threshold = Integer.MAX_VALUE;
    	    return;
    	}
    	
    	Entry[] newTable = new Entry[newCapacity];
    	transfer(newTable, initHashSeedAsNeeded(newCapacity));
    	table = newTable;
    	threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }
    

    如果数组进行扩容,数组长度发生变化,而存储位置 index = h&(length-1),index也可能会发生变化,需要重新计算index,我们先来看看transfer这个方法:

    void transfer(Entry[] newTable, boolean rehash) {
    	int newCapacity = newTable.length;
    	//for循环中的代码,逐个遍历链表,重新计算索引位置,将老数组数据复制到新数组中去(数组不存储实际数据,所以仅仅是拷贝引用而已)
    	 for (Entry<K,V> e : table) {
    	     while(null != e) {
    	         Entry<K,V> next = e.next;
    	         if (rehash) {
    	             e.hash = null == e.key ? 0 : hash(e.key);
    	         }
    	         int i = indexFor(e.hash, newCapacity);
    	         //将当前entry的next链指向新的索引位置,newTable[i]有可能为空,有可能也是个entry链,如果是entry链,直接在链表头部插入。
    	         e.next = newTable[i];
    	         newTable[i] = e;
    	         e = next;
    	     }
    	 }
    }
    

    这个方法将老数组中的数据逐个链表地遍历,扔到新的扩容后的数组中,我们的数组索引位置的计算是通过对key值的hashcode进行hash运算后,再通过和 length-1进行位运算得到最终数组索引位置。

    HashMap的数组长度一定保持2的次幂,比如16的二进制表示为 10000,那么length-1就是15,二进制为01111,同理扩容后的数组长度为32,二进制表示为100000,length-1为31,二进制表示为011111。

    从下图可以我们也能看到这样会保证低位全为1,而扩容后只有一位差异,也就是多出了最左位的1,这样在通过 h&(length-1)的时候,只要h对应的最左边的那位为0,则新的数组索引=老数组索引,如果h对应的最左边的那位为1,则新的数组索引=老数组索引+旧的数组容量,避免了新的数组索引的计算量。
    在这里插入图片描述

    第二,数组长度保持2的次幂,这样length-1的低位都为1,会使获得的数组索引index更加均匀,减少碰撞的几率。

    在这里插入图片描述
    如上图,如果容量是2的次幂,那么length-1的低位全为1,要得到index=21这个存储位置,h的低位只有这一种组合。

    如果容量不是2的次幂,那么length-1的低位也就不全为1,如下图,此时,这两个h值都会使得index=21
    在这里插入图片描述
    同时,index对应的这个bit位无论如何不会等于1了,而对应的那些数组位置也就被白白浪费了。

    即,如果容量不是2的次幂,就会造成分布不均匀了,增加了碰撞的几率,减慢了查询的效率,造成空间的浪费。

    get方法

    public V get(Object key) {
    	//如果key为null,则直接去table[0]处去检索即可。
    	if (key == null)
    	   return getForNullKey();
    	Entry<K,V> entry = getEntry(key);
    	return null == entry ? null : entry.getValue();
    }
    

    get方法通过key值返回对应value,如果key为null,直接去table[0]处检索。我们再看一下getEntry这个方法:

    final Entry<K,V> getEntry(Object key) {
                
    	if (size == 0) {
    	    return null;
    	}
    	//通过key的hashcode值计算hash值
    	int hash = (key == null) ? 0 : hash(key);
    	//indexFor (hash&length-1) 获取最终数组索引,然后遍历链表,通过equals方法比对找出对应记录
    	for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
    	    Object k;
    	    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
    	        return e;
    	}
    	return null;
    }    
    

    可以看出,get方法的实现相对简单,key(hashcode)–>hash–>indexFor–>最终索引位置,找到对应位置table[i],再查看是否有链表,遍历链表,通过key的equals方法比对查找对应的记录。要注意的是,有人觉得上面在定位到数组位置之后然后遍历链表的时候,e.hash == hash这个判断没必要,仅通过equals判断就可以。其实不然,试想一下,如果传入的key对象重写了equals方法却没有重写hashCode,而恰巧此对象定位到这个数组位置,如果仅仅用equals判断可能是相等的,但其hashCode和当前对象不一致,这种情况,根据Object的hashCode的约定,不能返回当前对象,而应该返回null,后面的例子会做出进一步解释。

    HashMap增加新元素的主要步骤

    HashMap 是如何使用 hash 函数的

    首先,我们来看一下在 HashMap 中,最常用的 put() 和 get() 是怎么使用 hash() 的。以下源码均为 jdk7。

    // put() 
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    
    // get()
    int hash = hash(key.hashCode());
    for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            return e.value;
    }
    

    我们不难观察到,HashMap 中都是先使用 hash 函数 获取一个 hash 值,然后利用得到的 hash 值和容器长度计算存放位置(indexFor() 方法)。接下来我们就详细看一下 hash() 和 indexFor() 两个方法。

    static int hash(int h) {
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
    
    static int indexFor(int h, int length) {
        return h & (length-1);
    }
    

    通过put() 和 get() 方法,我们可以知道,hash() 方法中的参数 h 就是 key 的 hashCode,hash() 方法对 hashCode 分别无符号右移 (>>>) 7 位和 4 位,并与自身进行异或(^)处理。 这么做的目的是什么?

    由于 indexFor() 返回的是 h(hash 值) 与 length-1(容器长度-1) 进行与运算的结果,若不进行扰动,即h = hashCode,将会很容易发生冲突。如下图所示,当低位相同时, h & (length - 1) 结果也会是一样的。

    在这里插入图片描述
    在经过扰动算法后,结果如下:
    在这里插入图片描述
    可以明显看到,计算出来的 hash 值是不一样的,即二者不会再发生冲突。这就是为什么 hash() 方法中要使用扰动算法:可以有效降低冲突概率。

    既然已经解决了 hash() 的计算问题,那么接下来就是计算索引了。HashMap 通过 hash 值与 length-1 (容器长度-1)进行取模(%)运算。可能有人会问:明明源码中 indexFor() 方法进行的 按位与(&)运算,而非取模运算。

    实际上,HashMap 中的 indexFor() 方法就是在进行取模运算。利用位运算代替取模运算,可以大大提高程序的计算效率。位运算可以直接对内存数据进行操作,不需要转换成十进制,因此效率要高得多。

    需要注意的是,只有在特定情况下,位运算才可以替换取模运算(当 b = 2^n时,a % b = a & (b - 1) )。也是因此,HashMap 才将初始长度设置为 16,且扩容只能是以 2 的倍数扩容。

    重写equals方法需同时重写hashCode方法

    最后我们再聊聊老生常谈的一个问题,各种资料上都会提到,“重写equals时也要同时覆盖hashcode”,我们举个小例子来看看,如果重写了equals而不重写hashcode会发生什么样的问题

    
    public class MyTest {
        private static class Person{
            int idCard;
            String name;
    
            public Person(int idCard, String name) {
                this.idCard = idCard;
                this.name = name;
            }
            @Override
            public boolean equals(Object o) {
                if (this == o) {
                    return true;
                }
                if (o == null || getClass() != o.getClass()){
                    return false;
                }
                Person person = (Person) o;
                //两个对象是否等值,通过idCard来确定
                return this.idCard == person.idCard;
            }
    
        }
        public static void main(String []args){
            HashMap<Person,String> map = new HashMap<Person, String>();
            Person person = new Person(1234, "乔峰");
            //put到hashmap中去
            map.put(person, "天龙八部");
            //get取出,从逻辑上讲应该能输出“天龙八部”
            System.out.println("结果:" + map.get(new Person(1234, "萧峰")));
        }
    }
    
    实际输出结果:null
    
    

    如果我们已经对HashMap的原理有了一定了解,这个结果就不难理解了。尽管我们在进行get和put操作的时候,使用的key从逻辑上讲是等值的(通过equals比较是相等的),但由于没有重写hashCode方法,所以put操作时,key(hashcode1)–>hash–>indexFor–>最终索引位置 ,而通过key取出value的时候 key(hashcode1)–>hash–>indexFor–>最终索引位置,由于hashcode1不等于hashcode2,导致没有定位到一个数组位置而返回逻辑上错误的值null(也有可能碰巧定位到一个数组位置,但是也会判断其entry的hash值是否相等,上面get方法中有提到。)

    所以,在重写equals的方法的时候,必须注意重写hashCode方法,同时还要保证通过equals判断相等的两个对象,调用hashCode方法时要返回同样的整数值。而如果equals判断不相等的两个对象,其hashCode可以相同(只不过会发生哈希冲突,应尽量避免)。

    出现哈希冲突时,新的节点是如何插入链表的

    Java8之前是使用头插法,Java8及之后使用尾插法

    链表转红黑树

    在Java8之前是没有红黑树的实现的,在jdk1.8中加入了红黑树,就是当链表长度为8时会将链表转换为红黑树,为6时又会转换成链表。

    JDK1.8中HashMap的性能优化

    假如一个数组槽位上的链表上数据过多(即拉链过长的情况)导致性能下降该怎么办?
    JDK1.8在JDK1.7的基础上增加了红黑树来进行优化。即当链表长度超过8时,链表就转换为红黑树,利用红黑树快速增删改查的特点提高HashMap的性能,其中会用到红黑树的插入、删除、查找等算法。

    三、面试常见问题

    1.说说HashMap原理

    2.加载因子为什么是0.75

    默认加载因子 0.75 在时间和空间开销上给出了一个较好的折衷。
    如果加载因子过大,空间开销少了,但会导致查找元素效率低;而过小则会导致空间开销大,数组利用率低,分布稀疏。
    具体的数值是通过牛顿二项式定理,求得了极限值(key接近无限大时) :log2 ≈ 0.693 (这个是在Stack Overflow找到的答案)

    3.为什么初始容量是16

    理论上2的整数次幂都行,但是,如果是2,4或者8会有点小,添加不了多少数据就会扩容,而扩容操作很影响性能。如果是32或者更大,那就浪费空间了。16是作为一个非常合适的经验值保留下来。

    4.容量为什么是2的次幂

    1)使获得的数组索引index更加均匀,减少碰撞的几率。如果容量是2的次幂,那么length-1的低位全为1,要得到特定index的存储位置,hash只有一种值,如果容量不是2的次幂,多个不同的hash值都可能得到同一个index,并且数组的某些存储位置上永远不可能有元素存储。

    2)如果容量是2的次幂,扩容时,新的数组索引要么=老数组索引,要么=老数组索引+旧的数组容量,避免了新的数组索引的计算量。

    3)当 b = 2^n时,a % b = a & (b - 1) ,位运算代替取模运算,可以大大提高程序的计算效率

    5.说说HashMap的扩容机制

    1)一旦扩容,所有元素都要重新移动到新的数组。

    2)加载因子loadFactor,阈值threshold
    当数组中元素个数>threshold(size > threshold)时进行扩容,threshold=capacity*loadFactor

    3)预估需要的节点数,new HashMap()时设置容量,从而避免扩容。比如,预估最多n个节点,则创建HashMap:

    HashMap hashMap = new HashMap(n/0.75 + 1)
    

    6.如何防止HashMap退化为单链表

    7.链表转化为红黑树的阈值为什么是8

    链表的查找效率为O(n),而红黑树的查找效率为O(logn),红黑树提高了查找效率,虽然红黑树的查找效率变高了,但是插入效率却变低了(插入元素时需要调整红黑树的结构),因此从一开始就用红黑树并不合适,需要选择一个临界值,临界值8是根据概率论的泊松分布计算出来的,根据概率论,哈希表的每个箱子中,元素的数量遵守泊松分布,当元素的数量为8时,概率已经很低了,因此,在正常的Hash算法下,红黑树结构基本不可能被构造出来。选择临界值为8时树化,性价比会很高,既不会因为链表太长(>8)导致复杂度加大,也不会因为树化概率太高导致太多节点树化。

    8.红黑树转化为链表的阈值为什么是6,而不是8

    9.准备用HashMap存1w条数据,构造HashMap时传10000会触发扩容吗?

    参考:
    HashMap实现原理分析

    Java集合之一—HashMap
    详解 HashMap 中的 hash 函数

    哈希冲突及四种解决方法
    Hash算法解决冲突的方法一般有以下几种常用的解决方法

    HashMap框架源码深入解读,面试不用愁
    害怕面试被问HashMap?这一篇就搞定了!
    一个HashMap跟面试官扯了半个小时

    一篇让你彻底搞懂HashMap,面试再也不怕了(文末有彩蛋)

    HashMap 源码理解
    HashMap源码分析——put和get(一)
    HashMap源码分析 —— put与get(四)
    搞懂 Java HashMap 源码

    面试官再问你 HashMap 底层原理,就把这篇文章甩给他看

    再也不怕面试问HashMap了
    【面试题】HashMap 底层实现原理是什么?JDK8 做了哪些优化?
    Java面试精选(20):你知道为什么HashMap是线程不安全的吗?
    Jdk1.8中的HashMap实现原理
    JDK7中HashMap存在的问题分析,你知道哪些?
    阿里P7岗位面试,面试官问我:为什么HashMap底层树化标准的元素个数是8
    面试官:为什么 HashMap 的加载因子是0.75?
    面试官:”准备用HashMap存1w条数据,构造时传10000会触发扩容吗?“
    Hash算法及HashMap底层实现原理
    HashMap的泊松分布

    展开全文
  • 一、什么是哈希表 数组:采用一段连续的存储单元来存储...线性链表:对于链表的新增,删除等操作(找到指定操作位置后),仅需处理结点间的引用即可,时间复杂度为O(1),而查找操作需要遍历链表逐一进行比对,复杂
  • 2.3.10 图像的平均值与其DFT 有什么联系? 88 2.3.11 一幅图像放缩后其DFT 会如何变化? 89 B2.8 什么是快速傅里叶变换? 92 2.3.12 DFT 有哪些优点和缺点? 93 2.3.13 可以有实值的DFT 吗? 94 2.3.14 可以有...
  • 《数据结构 1800题》

    热门讨论 2012-12-27 16:52:03
    11.下面的程序段中,对 x的赋值语句的频度为(C )【北京工商大学 2001 一、10(3)】 FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A. O(2n) B.O(n) C.O(n2) D.O(log2n) 12.程序段 FOR i:=n-1 ...
  • PC机中两者的处理过程有什么不同? 六、综合应用题(每题10,共20 ) 现有16K×1位的动态存储器芯片若干,欲构成64K×8位的存储器,试求: 所需动态RAM芯片个数。 画出该存储器组成的逻辑框图 设该...
  • 关于FFT的部分,其速度比Matlab的FFT算法快了不是一般的多,所以之后的滤波处理中都使用了FFT。 但是FFT的缺点是进行FFT运算前你必须要把图片大小转成2的幂数(我的软件自带缩放哦~),当然不一定要宽高相等,...
  • 更具体地说,管理经济学利用了经济工具和技术去分析和解决企业的各种经营管理问题。从某种意义上来讲管理经济学,如图211所示,传统经济学与经营管理决策学之间架起了一座桥梁。 □ 管理经济学与传统...
  • MAPGIS地质制图工具

    2013-05-06 16:15:30
    6、点存储,就会存储这个钻孔的数据,如果你还有钻孔,就继续另外一个钻孔位置点击一下,输入数据,点存储,如果没有了,就点退出。 7、输入探槽数据。选择读取探槽数据,探槽起点的地方点击一下,会出现探槽...
  • 15.2 数据学家机构中的位置 170 15.3 最后的想法 171 第16章 如何雇佣机器学习专家 172 16.1 确定问题 172 16.2 模型测试 173 16.3 创建训练集 174 16.4 选择特征 175 16.5 数据编码 176 16.6 训练集、...
  • •兼有段式和页式管理的优点,系统复杂和开销增大,一般在大型机器上才使用。 第五章文件管理 1、文件管理任务与功能 任务:把存储、检索、共享和保护文件的手段,提供给操作系统本身和用户,以达到方便...
  • 软件工程知识点

    2012-12-02 21:34:25
    软件定义是软件项目的早期阶段,主要由软件系统分析人员和用户合作,针对有待开发的软件系统进行分析、规划和规格描述,确定软件是什么,为今后的软件开发做准备。这个时期往往需要阶段地进行以下几项工作。 1....
  • 如果我们使用的硬盘是预定义以外的,那么就应该设置硬盘类型为USER,然后输入硬盘的实际参数(这些参数一般在硬盘的表面标签上);如果没有安装IDE设备,我们可以选择NONE参数,这样可以加快系统的启动速度,在一些...
  • 这个调查结果显示,2008年年底,超过百万级数据量的企业已经占到65.4%,超过千万级的超过37.1%,而仅仅一年中,超过亿级数据量的企业比2007年增长了5个百点。  从另一项“每个DBA管理的数据库数量”调查结果...
  • 根据已定的入端和出端交换网络上的位置(地址 码),选择一条空闲的通路。 输出处理的交换闷络驱动程序:输出处理机的输出信息找行内部任务或动相 关硬件设备 34程控父换机软件的基本特点是什么?有哪几部分红成? 答:...
  • 算学费输入数据求最大精确划分思维解决最大次大交换数据实现按行显示围棋棋盘绘制国际象棋绘制为什么要用函数函数的四种类型函数的一般形式必须用函数的理由-哥德巴赫函数的本质就是地址函数变量意义函数变量用途...
  • “卓越的全球城市,令人向往的创新之城、人文之城、生态之城,具有世界影响力的社会主义现代化国际大都市”,通过“创新、人文、生态”三个目标,深化了“卓越的全球城市”的内涵,充分体现创新对未来城市竞争力的...
  • 求100个人的高考成绩平均分与求全省所有考生的成绩平均分在占用时间和内存存储上有非常大的差异,我们自然追求高效率和低存储的算法来解决问题。 2.6.1正确性 22 2.6.2可读性 23 2.6.3健壮性 23 2.6.4时间效率高和...
  • 2009达内SQL学习笔记

    2010-02-10 19:46:58
    函数一般在数据上执行,它给数据的转换和处理提供了方便。不同的DBMS提供的函数不同。 函数可能会带来系统的不可移植性(可移植性:所编写的代码可以在多个系统上运行)。 加入注释是一个使用函数的好习惯。 大多数...
  • 他曾英国和欧洲的多家公司、政府部门和非政府组织供职,此后南非的Oracle大学工作数年。他具有数据库和应用服务器管理的OCP认证资格,IT从业经历达25年之久,曾编撰多本技术书籍,发表多篇技术论文。 目录 封面...
  • 求100个人的高考成绩平均分与求全省所有考生的成绩平均分在占用时间和内存存储上有非常大的差异,我们自然追求高效率和低存储的算法来解决问题。 2.6.1正确性 22 2.6.2可读性 23 2.6.3健壮性 23 2.6.4时间效率高和...
  • 大话数据结构

    2019-01-10 16:35:22
    求100个人的高考成绩平均分与求全省所有考生的成绩平均分在占用时间和内存存储上有非常大的差异,我们自然追求高效率和低存储的算法来解决问题。 2.6.1正确性 22 2.6.2可读性 23 2.6.3健壮性 23 2.6.4时间效率高和...
  • 大话数据结构 程杰

    2018-09-01 10:06:43
    求100个人的高考成绩平均分与求全省所有考生的成绩平均分在占用时间和内存存储上有非常大的差异,我们自然追求高效率和低存储的算法来解决问题。 2.6.1正确性 22 2.6.2可读性 23 2.6.3健壮性 23 2.6.4时间效率高和...
  • c++ 面试题 总结

    2009-09-16 08:44:40
    代码的位置必须物理内存中才能被运行,由于现在的操作系统中有非常多的程序运行着,内存中不能够完全放下,所以引出了虚拟内存的概念。把哪些不常用的程序片断就放入虚拟内存,当需要用到它的时候load入主存...
  • 2.5 算法的特性 21 2.5.1 输入输出 21 2.5.2 有穷性 21 2.5.3 确定性 21 2.5.4 可行性 21 2.6 算法设计的要求 22 求100个人的高考成绩平均分与求全省所有考生的成绩平均分在占用时间和内存存储上有非常大的差异,...
  • 2·1 约·通 2·2 分式的四则运算 2·3 繁分式 2·4 比例式 3. 无理数·无理式 3·1 平方根·不尽根数 3·2 开方法 3·3 无理数的计算 3·4 无理式的计算 4. 实数的绝对值 4·1 绝对值的意义·记号 4·2 含有...
  • 2·1 约·通 2·2 分式的四则运算 2·3 繁分式 2·4 比例式 3. 无理数·无理式 3·1 平方根·不尽根数 3·2 开方法 3·3 无理数的计算 3·4 无理式的计算 4. 实数的绝对值 4·1 绝对值的意义·记号 4·2 含有...

空空如也

空空如也

1 2
收藏数 39
精华内容 15
关键字:

平均分一般在什么位置