hashMap
java中用的比较多的底层结构有数组(也就是广义表结构)和链表。作为容器，他们各有优缺点。数组随机访问快但是增删慢。链表增删快，但是随机访问效率不高。那么有么有一种容器同时兼具访问快，增删快呢？有的就是hashMap。因为它的底层就是数组加链表！即entry[ ]桶数组里面装链表(entry对象的单向表,entry具有next属性，并存有key,value)
hashMap中的关键属性：
容量，数组的长度；
加载因子(决定数组何时扩容,默认0.75)；
阈值：加载因子*容量；
首先是一个基于散列表构建的Map。散列表就是具有一定关系映射的函数对照表。比如 定义一个 K， 在定义一个index。在定义K,index映射关系函数为F（index）=K+1,那么就可以理解（K,index）是一个散列表，映射函数为F。hashMap的k的哈希值的映射算法就是hash算法。简单的说就是一个对象进入map的时候，用hash算法算出它的hashCode。这个hashCode对容量取余之后的结果就是该对象在hashMap中桶的下标。如果又一个对象他的hashCode取余之后的下标重复了，那么这个enrty对象会被放入同一个桶中，同时后入桶的entry对象就会指向桶当前的entry对象，构成了就单向链表。
查询的时候 先把传入的key值hash一下计算下标，找到桶，如果产生碰撞即多个entry对象，就遍历链表或者红黑树（java1.8加入提高查询效率，减少查询开支,当链表长度超过阈值，链表转为红黑树）用equals（）去比较key值。找到对象。
这样就实现了增删和查询都快。
hashmap 线程不安全 效率高， hashtable线程安全 所有方法都加synchronize 效率低，
treemap可以自定义遍历顺序
linkhashmap可以按读取顺序来排列
concurrentHashMap 线程安全
底层实现：java1.7采用segment +hashEntry 既 分段锁数组和链表 锁住的是segment数组包含多个hashEntey链表
1.8采用 synchronize关键字+cas技术+hashEntry+红黑树
Synchronize只锁住首节点 粒度降低
网友评论