Map不同于Collection集合,Map存放的是键值对,且键不能重复
这篇博客主要讲集合的,哈希表这样的数据结构就不说明了,后期会补充哈希表,红黑树这样的博文
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 初始化桶容量16
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30; //最大容量2^31
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f; //默认装载因子,后面解释
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8; //当链表节点小于8个时,转成红黑树
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6; //树形元素小于6个时,转成链表
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
static final int MIN_TREEIFY_CAPACITY = 64; //桶的最小可能转化树形结构的大小
//链表的节点
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
//还重写了equals方法,可以看出键值相等才相等
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
634行 是解决null情况才加了判断
624行 大于8转成红黑树
652行 新值覆盖旧值,返回旧值
556行 为空返回null,否则返回节点的值
568行 计算的Hash值在桶上才行,而且桶不为空
573行 开始,遍历链表或者红黑树找相同的节点返回,没找到就返回Null
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
}
//删除节点的逻辑
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
和get方法差不多,先判断在不在桶上且或不为空
先去桶上找,找不到就遍历,遍历到了就记住这个节点
判断红黑树还是链表,执行各自删除节点操作
总结
/**
* A map entry (key-value pair). The <tt>Map.entrySet</tt> method returns
* a collection-view of the map, whose elements are of this class. The
* <i>only</i> way to obtain a reference to a map entry is from the
* iterator of this collection-view. These <tt>Map.Entry</tt> objects are
* valid <i>only</i> for the duration of the iteration; more formally,
* the behavior of a map entry is undefined if the backing map has been
* modified after the entry was returned by the iterator, except through
* the <tt>setValue</tt> operation on the map entry.
*
* @see Map#entrySet()
* @since 1.2
*/
interface Entry<K,V> {
boolean equals(Object o);
int hashCode();
public static <K extends Comparable<? super K>, V> Comparator<Map.Entry<K,V>> comparingByKey() {
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getKey().compareTo(c2.getKey());
}
}
static class Node<K,V> implements Map.Entry<K,V> {内容就不写了,参考上面}
有点混,捋捋就好
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);
}
}
是否访问顺序,默认构造函数为false
public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
//默认构造
public LinkedHashMap() {
super();
accessOrder = false;
}
返回值 | 方法名 | 解释 |
---|---|---|
Set< K> | keySet() | 返回包含所有key的Set集合 |
Set<Map.Entry<K,V>> | entrySet() | 返回包含所有entry的Set集合 |
//1.根据key集合访问
for (Object k : map.keySet()){
System.out.println(map.get(k));
}
//2.根据迭代器
Iterator iterator = map.entrySet().iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
//3.推荐,foreach,如果创建map集合指定了泛型就不用下面那么麻烦强转了
for(Map.Entry<Object,Object> entry : (Set<Map.Entry<Object, Object>>) map.entrySet()){
System.out.println(entry.getKey() + "=" +entry.getValue());
}
//新建结点
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e);
linkNodeLast(p); //因为创建结点的时候加入到维护的双向链表尾去了
return p;
}
//加入到链尾,开头变量维护了 head,和tail结点
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
//维护的变量
transient LinkedHashMap.Entry<K,V> head;
/**
* The tail (youngest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> tail;
按插入顺序
来访问,因为获取的entrySet()被重写了,获取的时是维护的链表set集合
LinkedHashMap<Integer,Integer> linkedHashMap = new LinkedHashMap();
linkedHashMap.put(1, 1);
linkedHashMap.put(2, 2);
linkedHashMap.put(3, 3);
linkedHashMap.put(4, 4);
linkedHashMap.put(5, 5);
for(Map.Entry entry : linkedHashMap.entrySet()){
System.out.println(entry);
}
1=1
2=2
3=3
4=4
5=5
按访问顺序
来访问,这里的get()就算是访问了
LinkedHashMap<Integer,Integer> linkedHashMap = new LinkedHashMap(10,0.75f,true);
linkedHashMap.put(1, 1);
linkedHashMap.put(2, 2);
linkedHashMap.put(3, 3);
linkedHashMap.put(4, 4);
linkedHashMap.put(5, 5);
//访问了3,所以结构被改变了
linkedHashMap.get(3);
for(Map.Entry entry : linkedHashMap.entrySet()){
System.out.println(entry);
}
1=1
2=2
4=4
5=5
3=3
总结
当需要键值对,且还需插入顺序
访问的时候采用LinkedHashMap,因为内部还要维护双向链表,损耗性能,不然对比二者推荐使用HashMap
608行 删除结点还是要平衡结点,很难,有兴趣去看看二叉查找树,平衡树,红黑树
构造方法
//默认构造没有比较器
public TreeMap() {
comparator = null;
}
//也可以传入比较器
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
继承关系
/**
* Returns the comparator used to order the keys in this map, or
* {@code null} if this map uses the {@linkplain Comparable
* natural ordering} of its keys.
*
* @return the comparator used to order the keys in this map,
* or {@code null} if this map uses the natural ordering
* of its keys
*/
Comparator<? super K> comparator();
遍历
利用父类的successor遍历树
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
if (t == null)
return null;
else if (t.right != null) {
Entry<K,V> p = t.right;
while (p.left != null)
p = p.left;
return p;
} else {
Entry<K,V> p = t.parent;
Entry<K,V> ch = t;
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
Set集合底层用的就是Map,所以看过Map集合后再来看Set集合简直太简单,下面看看怎么使用Map集合
其余都和HashMap一致,不再赘述
总结
Set集合和Map集合一样,那就没什么好说的了