2、链地址法
当装填因子是1时,大约三分之一的单元是空白单元,三分之一的单元有一个数据项,三分之一的单元有两个或更多的数据项。
链地址法装填因子可以达到1以上,对性能影响并不大;找到初始单元需要O(1)的时间级,搜索链表的时间与链表的平均数据项成正比。
当表容量不是质数时,还是能够导致聚集
哈希表优点
哈希表比树快,插入、查找、删除时间复杂度都接近O(1)。
缺点:
1、基于数组,难于扩展
2、无序
public Hashtable() {
this(11, 0.75f);
}
new Hashtable时我们输入的容量是多少就会创建多大的数组
扩展容量,2倍+1,int newCapacity = (oldCapacity << 1) + 1;
Hashtable的哈希方法用到了取模运算
如果hash和key都相同,覆盖value的值
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
HashMap
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
默认容量16,1 << 4; 最大容量,1 << 30; 负载因子,不指定默认0.75f;
初始容量,由tableSizeFor()方法确定,该方法返回值总是2的幂,传入7,返回8;传入13,返回16。
计算下标,i = (n - 1) & hash,i是下标,n是数组容量,hash是hash值
扩容
if (oldCap >= MAXIMUM_CAPACITY) {
原数组长度大于最大容量(1073741824) 则将threshold设为Integer最大值2147483647
threshold = Integer.MAX_VALUE;
return oldTab;
}
数组容量扩展至原来的两倍,阈值也扩展至原来的两倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
// 冲突了
else {
// 相同的key,先比较hash,再比较key
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果链表元素大于等于8个,把数据放入一个红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
// 红黑树
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
// 如果是key相同,会把新的value覆盖旧的value
e.value = value;
afterNodeAccess(e);
// 并返回旧的value
return oldValue;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 比较hash,且比较key,如果相同,就返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
// 判断是不是红黑树
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
按位与都为1结果为1;按位或有一个是1结果就是1;异或,不同为1,相同为0
HashSet由哈希表实现
// 无参构造方法
public HashSet() {
map = new HashMap<>();
}
// 有参构造方法
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
// 有参构造方法,创建的是一个LinkedHashMap
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
// /?preznt/ 现在的
private static final Object PRESENT = new Object();
public boolean add(E e) {
/* 如果e是重复的,也就是key相同,
* HashMap会用新的value覆盖旧的value,
* 但在这里其实两个value是一样的,都是PRESENT
* 接着返回旧的value,不等于null,最后返回false
*/
return map.put(e, PRESENT)==null;
}
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
LinkedHashMap既是一个HashMap,也是一个双端双向链表
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
transient LinkedHashMap.Entry<K,V> head;
transient LinkedHashMap.Entry<K,V> tail;
// HashMap.Node
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
Collections 是一个操作 Set、List 和 Map 等集合的工具类。
Collections 中提供了一系列静态的方法对集合元素进行排序、查询和修改等操作,还提供了对集合对象设置不可变、对集合对象实现同步控制等方法。
Collections类中的方法有:
sort()、binarySearch()、reverse() —— 反转、shuffle() —— 乱序
min()、max()、copy()、swap(List,int, int)
int frequency(Collection,Object):返回指定集合中指定元素的出现次数
boolean replaceAll(List list,Object oldVal,Object newVal):使用新值替换 List 对象的所有旧值
List的实现类:ArrayList、LinkedList、Vector,Stack是Vector的一个子类。
Dictionary被Map取代,Hashtable实现了Dictionary,Properties是Hashtable的一个子类;Properties的key和value都是字符串类型。
Properties properties = System.getProperties();
数组,新增快,查询慢O(N),插入删除慢O(N)