微信视频网站建设多少钱,福州网站建设价格,个人备案网站可以做电商吗,百度seo是啥目录数组链表#xff1a;存在性能最坏情况O(n)Java7的HashMap的put方法思路数组链表红黑树#xff1a;性能提高到O(logn)Java8的HashMap的putVal方法思路数组链表#xff1a;存在性能最坏情况O(n)
Java8以前#xff0c;HashMap底层数据结构采用数组链表的结构。 数组特点链表存在性能最坏情况O(n)Java7的HashMap的put方法思路数组链表红黑树性能提高到O(logn)Java8的HashMap的putVal方法思路数组链表存在性能最坏情况O(n)
Java8以前HashMap底层数据结构采用数组链表的结构。 数组特点查询快增删慢。 链表特点查询慢增删较快。 HashMap结合了数组和链表的优势。同时HashMap的操作是非Synchronized因此效率比较高。
Java7的HashMap的put方法思路
put源码
public V put(K key, V value) {if (table EMPTY_TABLE) {inflateTable(threshold);}if (key null)return putForNullKey(value);int hash hash(key);int i indexFor(hash, table.length);for (EntryK,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;}addEntry源码
/*** Adds a new entry with the specified key, value and hash code to* the specified bucket. It is the responsibility of this* method to resize the table if appropriate.** Subclass overrides this to alter the behavior of put method.*/void addEntry(int hash, K key, V value, int bucketIndex) {if ((size threshold) (null ! table[bucketIndex])) {resize(2 * table.length);hash (null ! key) ? hash(key) : 0;bucketIndex indexFor(hash, table.length);}createEntry(hash, key, value, bucketIndex);}方法简述 1、初始化HashMap若Entry数组类型的table为空inflated膨胀扩容意思一个tablethreshold默认初始容量16 2、对key求Hash值然后再计算table下标 3、如果没有碰撞即数组中没有相应的键值对直接放入桶bucket中如果碰撞了以链表的方式链接到后面 4、如果键值对已经存在就替换旧值 5、如果桶满了容量16*加载因子0.75就需要扩容resize();
但是存在坏情况如果通过哈希散列运算得到的是同一个值即总是分配到同一个桶中使某个桶的链表长度很长。 由于链表查询需要从头开始遍历最坏情况下HashMap性能变为O(n)。
数组链表红黑树性能提高到O(logn)
Java8以后HashMap底层数据结构采用数组链表红黑树的结构。 通过常量TREEIFY_THRESHOLD8和UNTREEIFY_THRESHOLD6来控制链表与红黑树的转化。
Java8的HashMap的putVal方法思路
putVal源码
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {NodeK,V[] tab; NodeK,V p; int n, i;if ((tab table) null || (n tab.length) 0)n (tab resize()).length;if ((p tab[i (n - 1) hash]) null)tab[i] newNode(hash, key, value, null);else {NodeK,V e; K k;if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))e p;else if (p instanceof TreeNode)e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value);else {for (int binCount 0; ; binCount) {if ((e p.next) null) {p.next newNode(hash, key, value, null);if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))break;p e;}}if (e ! null) { // existing mapping for keyV oldValue e.value;if (!onlyIfAbsent || oldValue null)e.value value;afterNodeAccess(e);return oldValue;}}modCount;if (size threshold)resize();afterNodeInsertion(evict);return null;}在Java7源码基础上增加了链表和红黑树的转化。 如果链表长度超过阈值8就把链表转换成红黑树如果链表长度低于6就把红黑树转回链表。改变了最坏情况下O(n)性能提高到O(logn)。 注意Java7中数组里的元素叫EntryJava8及以后改名为Node节点。
