查营业执照怎么查询,深圳市企业网站seo联系方式,芬兰网站后缀,天元建设集团有限公司张桂玉丑闻Hashmap本质是数组加链表。根据key取得hash值#xff0c;然后计算出数组下标#xff0c;如果多个key对应到同一个下标#xff0c;就用链表串起来#xff0c;新插入的在前面。 ConcurrentHashMap#xff1a;在hashMap的基础上#xff0c;ConcurrentHashMap将数据分为多个s… Hashmap本质是数组加链表。根据key取得hash值然后计算出数组下标如果多个key对应到同一个下标就用链表串起来新插入的在前面。 ConcurrentHashMap在hashMap的基础上ConcurrentHashMap将数据分为多个segment默认16个concurrency level然后每次操作对一个segment加锁避免多线程锁的几率提高并发效率。 一、HashMap概述 HashMap基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作并允许使用 null 值和 null 键。除了不同步和允许使用 null 之外HashMap 类与 Hashtable 大致相同。此类不保证映射的顺序特别是它不保证该顺序恒久不变。 值得注意的是HashMap不是线程安全的如果想要线程安全的HashMap可以通过Collections类的静态方法synchronizedMap获得线程安全的HashMap。 1 Map map Collections.synchronizedMap(new HashMap()); 二、HashMap的数据结构 HashMap的底层主要是基于数组和链表来实现的它之所以有相当快的查询速度主要是因为它是通过计算散列码来决定存储的位置能够很快的计算出对象所存储的位置。HashMap中主要是通过key的hashCode来计算hash值的只要hashCode相同计算出来的hash值就一样。如果存储的对象对多了就有可能不同的对象所算出来的hash值是相同的这就出现了所谓的hash冲突。学过数据结构的同学都知道解决hash冲突的方法有很多HashMap底层是通过链表来解决hash冲突的。 从上图中可以看出HashMap底层就是一个数组结构数组中存放的是一个Entry对象如果产生的hash冲突也就是说要存储的那个位置上面已经存储了对象了这时候该位置存储的就是一个链表了。我们看看HashMap中Entry类的代码 1 static class EntryK,V implements Map.EntryK,V {2 final K key;3 V value;4 EntryK,V next;5 final int hash;6 7 /**8 * Creates new entry.9 */
10 Entry(int h, K k, V v, EntryK,V n) {
11 value v;
12 next n; //hash值冲突后存放在链表的下一个
13 key k;
14 hash h;
15 }
16
17 .........
18 } HashMap其实就是一个Entry数组Entry对象中包含了键和值其中next也是一个Entry对象它就是用来处理hash冲突的形成一个链表。 三、HashMap源码分析 先看看HashMap类中的一些关键属性 1 transient Entry[] table;//存储元素的实体数组
2
3 transient int size;//存放元素的个数
4
5 int threshold; //临界值 当实际大小超过临界值时会进行扩容threshold 加载因子*容量
6
7 final float loadFactor; //加载因子
8
9 transient int modCount;//被修改的次数 其中加载因子是表示Hash表中元素的填满的程度.若:加载因子越大,填满的元素越多,好处是,空间利用率高了,但:冲突的机会加大了.反之,加载因子越小,填满的元素越少,好处是:冲突的机会减小了,但:空间浪费多了.冲突的机会越大,则查找的成本越高.反之,查找的成本越小.因而,查找时间就越小.因此,必须在 冲突的机会与空间利用率之间寻找一种平衡与折衷. 这种平衡与折衷本质上是数据结构中有名的时-空矛盾的平衡与折衷. 如果机器内存足够并且想要提高查询速度的话可以将加载因子设置小一点相反如果机器内存紧张并且对查询速度没有什么要求的话可以将加载因子设置大一点。不过一般我们都不用去设置它让它取默认值0.75就好了。 下面看看HashMap的几个构造方法 1 public HashMap(int initialCapacity, float loadFactor) {2 //确保数字合法3 if (initialCapacity 0)4 throw new IllegalArgumentException(Illegal initial capacity: 5 initialCapacity);6 if (initialCapacity MAXIMUM_CAPACITY)7 initialCapacity MAXIMUM_CAPACITY;8 if (loadFactor 0 || Float.isNaN(loadFactor))9 throw new IllegalArgumentException(Illegal load factor:
10 loadFactor);
11
12 // Find a power of 2 initialCapacity
13 int capacity 1; //初始容量
14 while (capacity initialCapacity) //确保容量为2的n次幂使capacity为大于initialCapacity的最小的2的n次幂
15 capacity 1;
16
17 this.loadFactor loadFactor;
18 threshold (int)(capacity * loadFactor);
19 table new Entry[capacity];
20 init();
21 }
22
23 public HashMap(int initialCapacity) {
24 this(initialCapacity, DEFAULT_LOAD_FACTOR);
25 }
26
27 public HashMap() {
28 this.loadFactor DEFAULT_LOAD_FACTOR;
29 threshold (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
30 table new Entry[DEFAULT_INITIAL_CAPACITY];
31 init();
32 } 我们可以看到在构造HashMap的时候如果我们指定了加载因子和初始容量的话就调用第一个构造方法否则的话就是用默认的。默认初始容量为16默认加载因子为0.75。我们可以看到上面代码中13-15行这段代码的作用是确保容量为2的n次幂使capacity为大于initialCapacity的最小的2的n次幂至于为什么要把容量设置为2的n次幂我们等下再看。 下面看看HashMap存储数据的过程是怎样的首先看看HashMap的put方法 1 public V put(K key, V value) {2 if (key null) //如果键为null的话调用putForNullKey(value)3 return putForNullKey(value);4 int hash hash(key.hashCode());//根据键的hashCode计算hash码5 int i indexFor(hash, table.length);6 for (EntryK,V e table[i]; e ! null; e e.next) { //处理冲突的如果hash值相同则在该位置用链表存储7 Object k;8 if (e.hash hash ((k e.key) key || key.equals(k))) { //如果key相同则覆盖并返回旧值9 V oldValue e.value;
10 e.value value;
11 e.recordAccess(this);
12 return oldValue;
13 }
14 }
15
16 modCount;
17 addEntry(hash, key, value, i);
18 return null;
19 } 当我们往hashmap中put元素的时候先根据key的hash值得到这个元素在数组中的位置即下标然后就可以把这个元素放到对应的位置中了。如果这个元素所在的位子上已经存放有其他元素了那么在同一个位子上的元素将以链表的形式存放新加入的放在链头最先加入的放在链尾。从hashmap中get元素时首先计算key的hashcode找到数组中对应位置的某一元素然后通过key的equals方法在对应位置的链表中找到需要的元素。 具体的实现是 当你的key为null时会调用putForNullKey,HashMap允许key为null,这样的对像是放在table[0]中。 如果不为空则调用int hash hash(key.hashCode());这是hashmap的一个自定义的hash,在key.hashCode()基础上进行二次hash 1 static int hash(int h) {
2 h ^ (h 20) ^ (h 12);
3 return h ^ (h 7) ^ (h 4);
4 } 得到hash码之后就会通过hash码去计算出应该存储在数组中的索引计算索引的函数如下 1 static int indexFor(int h, int length) {
2 return h (length-1);
3 } 这个方法非常巧妙它通过 h (table.length -1) 来得到该对象的保存位而HashMap底层数组的长度总是 2 的n 次方这是HashMap在速度上的优化。当length总是 2 的n次方时h (length-1)运算等价于对length取模也就是h%length但是比%具有更高的效率。当数组长度为2的n次幂的时候不同的key算得得index相同的几率较小那么数据在数组上分布就比较均匀也就是说碰撞的几率小相对的查询的时候就不用遍历某个位置上的链表这样查询效率也就较高了。 下面我们继续回到put方法里面前面已经计算出索引的值了看到第6到14行如果数组中该索引的位置的链表已经存在key相同的对象则将其覆盖掉并返回原先的值。如果没有与key相同的键则调用addEntry方法创建一个Entry对象addEntry方法如下 1 void addEntry(int hash, K key, V value, int bucketIndex) {
2 EntryK,V e table[bucketIndex]; //如果要加入的位置有值将该位置原先的值设置为新entry的next,也就是新entry链表的下一个节点
3 table[bucketIndex] new Entry(hash, key, value, e);
4 if (size threshold) //如果大于临界值就扩容
5 resize(2 * table.length); //以2的倍数扩容
6 } 参数bucketIndex就是indexFor函数计算出来的索引值第2行代码是取得数组中索引为bucketIndex的Entry对象第3行就是用hash、key、value构建一个新的Entry对象放到索引为bucketIndex的位置并且将该位置原先的对象设置为新对象的next构成链表。 第4行和第5行就是判断put后size是否达到了临界值threshold如果达到了临界值就要进行扩容HashMap扩容是扩为原来的两倍。resize()方法如下 1 void resize(int newCapacity) {2 Entry[] oldTable table;3 int oldCapacity oldTable.length;4 if (oldCapacity MAXIMUM_CAPACITY) {5 threshold Integer.MAX_VALUE;6 return;7 }8 9 Entry[] newTable new Entry[newCapacity];
10 transfer(newTable);//用来将原先table的元素全部移到newTable里面
11 table newTable; //再将newTable赋值给table
12 threshold (int)(newCapacity * loadFactor);//重新计算临界值
13 } 扩容是需要进行数组复制的上面代码中第10行为复制数组复制数组是非常消耗性能的操作所以如果我们已经预知HashMap中元素的个数那么预设元素的个数能够有效的提高HashMap的性能。转载于:https://www.cnblogs.com/remember-forget/p/6021644.html
