散列表:hashmap
,hashtable
,concurrentHashmap
树:hashset
,treemap
,treeset
jdk7中hashMap采用数组+链表,如果过多的节点在hash时发生碰撞,如果要查找其中一个节点,需要O(n)的查找时间。
jdk7中hashMap采用数组+链表/红黑树,当某个桶位达到某个阈值时,链表将转化为红黑树,红黑树时间复杂度O(nlogn)
1.开放定址法: 通过探测算法,当一个槽位已经被占用情况下继续查找下一个
2.链地址法(数组+链表)
3.再哈希 准备多个散列函数,当发生冲突时,再选择一个散列函数进行散列。
HashMap 底层是数组和单向链表实现,数组中的每个元素都是链表,由 Node 内部类(实现 Map.Entry<K,V>接口)实现,HashMap 通过 put & get 方法存储和获取。
HashCode是定位(存储位置),equals是定性(两者是否相等)
1.存储对象时,将K/V传给put()方法:
2.hash(K)计算K的hash,结合数组长度,计算数组下标
调整数据大小(当容器中的元素个数大于 capacity * loadfactor 时,容器会进行扩容resize 为 2n)
3.三种情况:
获取对象时(get方法):
转载于:https://my.oschina.net/u/3973793/blog/3100006