HashMap:
数组与链表,每个数据对应一个链表
插入时进行与运算
http://blog.csdn.net/tingting256/article/details/52475422
数组默认长度16,当超过16*0.75=12时,组数长度变为16*2->叫resize,毁
HashMap的基础构造器HashMap(int initialCapacity, float loadFactor)带有两个参数,它们是初始容量initialCapacity和加载因子loadFactor。
https://www.cnblogs.com/ITtangtang/p/3948406.html
相同含义的两个对象,插入同一个key:
http://blog.csdn.net/zbuger/article/details/51029898
为什么数据是2的n次幂
为了更均匀打到槽点。与运算
http://www.cnblogs.com/ysocean/p/9054804.html
当 lenth = 2n 时,X % length = X & (length - 1) ,模运算 % 可以变换为按位与 & 运算
早期版本是直接取模%,后期改为位运算
一个十进制数对一个2n 的数取余,我们可以将这个十进制转换为二进制数,将这个二进制数右移n位,移掉的这 n 位数即是余数。
为什么是数组长度是16
计算卡槽点时,具体落到哪个数组时,做与运算时
hash(hashCode(key)) & (length-1) -> 会落到位置范围内
二进制:Interger.toBinaryString(15);
容量到了12会扩容:在扩容的时候更多的节点不需要重新计算到新槽点, hash之后的桶的角标是不变的。
为什么0.75
过低,小一点:扩容频繁。
过高,大一点:扩容不容易发生,数组重复概率增加,导致get和put时间增多,冲突需要遍历大量链表空间。
final int hash(Object key)里有>>>,>>>
降低重复冲突概率
深入理解:
https://www.zhihu.com/question/20733617
“扰动函数”混合原始哈希码的高位和低位,加大低位随机性,为了减少数组碰撞概率,减少10%。
Java 8觉得扰动做一次就够了,做4次的话,多了可能边际效用也不大,所谓为了效率考虑就改成一次了。
当获取对象时get,hash找到数组槽位,循环链表,通过键对象key的equals()方法找到正确的键值对,然后返回值对象。
HashTable:
数组默认长度11
http://blog.csdn.net/xuefeng0707/article/details/40834595
继承的父类不同
线程安全性不同
key和value是否允许null值
hash值不同,插入算法也不同,hashtable取取模运算,hashmap与运算。
是否提供contains方法
http://blog.csdn.net/fujiakai/article/details/51585767
ConcurrentHashMap:
http://blog.csdn.net/yan_wenliang/article/details/51029372
segment数组,每个数组是一个hashtable,里面有分段锁
多线程put时,当同一数组存储时线程加锁,不同数组时,没有锁,效率的提升。
分享到:
相关推荐
8.HashMap的数据结构? 9.JDK1.8新增红黑树? 10.能否使用任何类作为 Map 的 key? 11.为什么HashMap中String、Integer这样的包装类适合作为K? 12.如果使用Object作为HashMap的Key,应该怎么办呢? 13.HashMap为...
1.7中的数据结构图:先来看看1.7中的实现。这是HashMap中比较核心的几个成员变量;看看分别是什么意思?初始化桶大小,因为底层是数组,所以这是数组默认的大小。桶最大值。默认的负载因子(0.75)table真正存放数据...
阿里面试题:ConcurrentHashMap为什么是线程安全的?...jdk1.7 ConcurrentHashMap数据结构 jdk1.7 ConcurrentHashMap是由一个Segment数组和多个HashEntry数组组成 其实就是将HashMap分为多个小HashMap,每个Segme
hashMap数据结构的优化,原来的hashMap采用的数据结构是哈希表(数组+链表),hashMap默认大小是16,一个0-15索引的数组,如何往里面存储元素,首先调用元素的hashcode方法,计算出哈希码值,经过哈希算法算成数组的...
• 熟悉常用集合数据结构(数组、Hashmap、ConcurrentHashMap、HashTable、ArrayList、Vetor、LinkedList、HashSet、TreeSet、LinkedHashSet),了解AVL、RBtree、B/B+树、跳表 • 熟悉常见异常分类以及处理,熟悉反射...
在jdk1.8中对hashMap等map集合的数据结构优化。hashMap数据结构的优化 原来的hashMap采用的数据结构是哈希表(数组+链表),hashMap默认大小是16,一个0-15索引的数组,如何往里面存储元素,首先调用元素的hashcode...
在jdk1.8中对hashMap等map集合的数据结构优化。hashMap数据结构的优化 原来的hashMap采用的数据结构是哈希表(数组+链表),hashMap默认大小是16,一个0-15索引的数组,如何往里面存储元素,首先调用元素的hashcode ...
18.HashMap底层数据结构 19.说说HashMap如何处理碰撞的,或者说说它的扩容? 20.jdk7/8中对HashMap做了哪些改变? 21.负载因子为什么会影响HashMap性能 22.为什么HashMap中initailCapacity要设置成2的n次幂 23....
leetcode下载 目录 操作系统 虚拟内存与物理内存转化 CPU 调度方式 进程栈大小 进程与线程区别 ...数据结构 Queue HashMap HashTable ConcurrentHashMap JAVA IO Go Redis Redis Cluster Redis 持久化方式 Redis
通过对HashMap的不同问题进行深入分析,读者可以全面了解该数据结构的工作原理和使用注意事项。 首先,文档解释了为什么HashMap选择红黑树作为数据结构,而不是其他结构,主要是因为红黑树在处理哈希冲突时具有更快...
通过对HashMap的不同问题进行深入分析,读者可以全面了解该数据结构的工作原理和使用注意事项。 首先,文件解释了为什么HashMap选择红黑树作为数据结构,而不是其他结构,主要是因为红黑树在处理哈希冲突时具有更快...
一、数据结构与算法 数据结构与算法 排序算法、动态规划、递归、回溯法、贪心算法等。 二、Java Java 基础概念 基本概念、面相对象、关键字、基本数据类型与运算、字符串与数组、异常处理、Object通用方法 Java ...
用什么数据结构实现的 加载因子是什么 HashMap 初始化传入的容量参数的值是就是 HashMap 实际分配的空间么 HashMp 的扩容机制是什么,什么时候扩容,每次扩多少 HashMap 的 get 过程是? HashMap 有什么缺点 谈谈你...
1.8 之后 hashMap 的数据结构发生了变化,从之前的单纯的数组+链表结构变成数组+链 表+红黑树。也就是说在 JVM 存储 hashMap 的 K-V 时仅仅通过 key 来决定每一个 entry 的存 储槽位(Node[]中的 index)。并且 ...
数据结构 Linux运维 P8架构 面试题汇总 目录 :面向对象,集合,IO流等 :HashMap,ConcurrentHashMap扩容原理等 :线程状态,ThreadLocal,强软弱虚引用,自定义线程池 :类加载过程,双亲委派机制 :syncro
从jdk1.7 之前 和hashMap的数据结构 和链表的插入方式 死链 谈到 jdk1.8的数据结构 和链表的改进,扩容方式 和触发扩容的条件。 4、为什么使用ConcurrentHashMap? 因为前面提了hashmap是线程不安全的容器,如果要...
数据结构与算法 数据结构 算法 数据库 MySQL Redis 系统设计 常用框架 Spring ZooKeeper 权限认证 设计模式 数据通信 网站架构 面试指南 备战面试 常见面试题总结 (为什么 Java 中只有值传递、==与equals、 hashCode...
数据结构与算法:最常见的各种排序,最好能手写 .. Java 高级:JVM 内存结构、垃圾回收器、回收算法、GC、并发编程相关(多 线程、线程池等)、NIO/BIO、各种集合类的比较优劣势(底层数据结构也要 掌握,特别是扩容等)...
数据结构与算法 各种树 B-树与B+树 (应用于MongoDB) (应用于MySQL) 算法 设计模式 补充阅读: JVM Java 进程 & 线程 & 协程 HashMap & ConcurrentHashMap JAVA自定义注解详解 JAVA其他知识点 并发 分布式 服务器 ...
Stairs).md](Java基础/数据结构与算法/LeetCode/LeetCode 70. 爬楼梯(Climbing Stairs).md) 7月3号 java 异常详解 7月2号 整理基础算法 7月1号 七月 6月30号 6月29号 6月25号 6月22号 Redis中String、List、Hash...