HashMap
- Map与Collection并列存在。用于保存具有映射关系的数据：Key-Value
- Map中的key和value可以是任何引用类型，会封装到HashMap$Node对象中
- Map中的key不允许重复，原因和HashSet一样，前面分析过源码
- Map中的value可以重复
- Map的key可以是null，value也可以为null，注意key为null只能有一个，value为null可以多个
- 常用String类作为Map的key
- key和value之间存在单向一对一关系，即通过指定的key总能找到对应的value
- 和HashSet一样，不保证映射的顺序，因为底层是以hash表的方式来存储
- HashMap没有实现同步，因此是线程不安全的，方法没有做同步互斥的操作，没有synchronized
Map接口的特点：
Map存放数据的key-value示意图，一对k-v是放在HashMap$Node的，又因为Node实现了Entry接口，有些书也说一对k-v就是一个Entry。
k-v最后是
HashMap$Node node = newNode(hash, key, value, null);k-v为了方便程序员的遍历，还会创建EntrySet集合，该集合存放的元素的类型Entry，而一个Entry对象就有k，v，EntrySet<Entry
<K,V>>
transient Set<Map.Entry<K,V>> entrySet;entrySet中，定义的类型是Map.Entry,但是实际上存放的还是HashMap$Node,这是因为
static class Node<K,V> implements Map.Entry<K,V>当把HashMap$Node对象存放到entrySet就方便我们的遍历，因为Map.Entry提供了重要方法
public final K getKey()
public final V getValue()
Map的六大遍历方式：
package map;
import java.util.Collection;
import java.util.HashMap;
import java.util.Set;
public class HashMapDemo {
public static void main(String[] args) {
HashMap<String, String> map = new HashMap<String, String>();
// 键不能重复，值可以重复
map.put("san", "张三");
map.put("si", "李四");
map.put("wu", "王五");
map.put("wang", "老王");
map.put("wang", "老王2");// 老王被覆盖
map.put("lao", "老王");
System.out.println("-------直接输出hashmap:-------");
System.out.println(map);
/**
* 遍历HashMap
*/
// 1.获取Map中的所有键
System.out.println("-------foreach获取Map中所有的键:------");
Set<String> keys = map.keySet();
for (String key : keys) {
System.out.print(key+" ");
}
System.out.println();//换行
// 2.获取Map中所有值
System.out.println("-------foreach获取Map中所有的值:------");
Collection<String> values = map.values();
for (String value : values) {
System.out.print(value+" ");
}
System.out.println();//换行
// 3.得到key的值的同时得到key所对应的值
System.out.println("-------得到key的值的同时得到key所对应的值:-------");
Set<String> keys2 = map.keySet();
for (String key : keys2) {
System.out.print(key + "：" + map.get(key)+" ");
}
/**
* 如果既要遍历key又要value，那么建议这种方式，因为如果先获取keySet然后再执行map.get(key)，map内部会执行两次遍历。
* 一次是在获取keySet的时候，一次是在遍历所有key的时候。
*/
// 当我调用put(key,value)方法的时候，首先会把key和value封装到
// Entry这个静态内部类对象中，把Entry对象再添加到数组中，所以我们想获取
// map中的所有键值对，我们只要获取数组中的所有Entry对象，接下来
// 调用Entry对象中的getKey()和getValue()方法就能获取键值对了
Set<java.util.Map.Entry<String, String>> entrys = map.entrySet();
for (java.util.Map.Entry<String, String> entry : entrys) {
System.out.println(entry.getKey() + "--" + entry.getValue());
}
/**
* HashMap其他常用方法
*/
System.out.println("after map.size()："+map.size());
System.out.println("after map.isEmpty()："+map.isEmpty());
System.out.println(map.remove("san"));
System.out.println("after map.remove()："+map);
System.out.println("after map.get(si)："+map.get("si"));
System.out.println("after map.containsKey(si)："+map.containsKey("si"));
System.out.println("after containsValue(李四)："+map.containsValue("李四"));
System.out.println(map.replace("si", "李四2"));
System.out.println("after map.replace(si, 李四2):"+map);
}
}源码分析：
- HashMap底层维护了Node类型的数组table，默认为null
- 当创建对象时，将加载因子初始化为0.75
- 当添加key val，通过key的哈希值得到在table的索引。然后判断该索引处是否有元素，如果没有元素直接添加。如果该索引处有元素，继续判断该元素的key是否和准备加入的key相等，如果相等，则直接替换val；如果不相等需要判断时树结构还是链表结构，做出相应处理。如果添加时发现容量不够，则需要扩容。
- 第一次添加，则需要扩容table容量为16，临界值为12
- 以后再扩容，则需要扩容table容量为原来的2倍，临界值为原来的2倍，即24，依次类推
- 在java8中，如果一条链表的元素个数超过8（默认），并且table的大小大于等于64（默认），就会进行树化（红黑树）
具体分析和HashSet源码相同，链接在此
Hashtable
- 存放的元素时键值对：即 K-V
- hashtable的键和值都不能为null，否则会抛出空指针异常
- hashTable使用方法基本上和HashMap一样
- hashTable是线程安全的，hashMap是线程不安全的
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializablepublic synchronized V put(K key, V value)底层有数组 Hashtable $ Entry[] 初始化为11
private static class Entry<K,V> implements Map.Entry<K,V>threshold 8 = 11 * 0.75
分析扩容源码：
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
//添加K-V 封装到Entry
addEntry(hash, key, value, index);
return null;
}private void addEntry(int hash, K key, V value, int index) {
modCount++;
Entry<?,?> tab[] = table;
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
//扩容
rehash();
tab = table;
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++;
}protected void rehash() {
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;
// overflow-conscious code
//关键点：新的容量 11 * 2 + 1 = 23
int newCapacity = (oldCapacity << 1) + 1;
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)
// Keep running with MAX_ARRAY_SIZE buckets
return;
newCapacity = MAX_ARRAY_SIZE;
}
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
modCount++;
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap;
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = (Entry<K,V>)newMap[index];
newMap[index] = e;
}
}
}HashMap与Hashtable的对比：
Properties
- 继承自Hashtable类并且实现了Map接口，也是使用键值对的形式来保存数据
- 使用特定和Hashtable类似
- 还可用于从 xxx.properties 文件通常作为配置文件，这个知识点在IO流举例
TreeSet
当我们使用无参构造器创建TreeSet时，仍然时无序的
老师希望添加的元素按照字符串大小来排序
使用TreeSet提供的一个构造器，可以传入一个比较器
new TreeSet<>(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
return ((String)o1).compareTo((String) o2);
}
});构造器把传入的比较器对象，赋给了TreeSet的底层的TreeMap的属性this.comparator
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}Comparator<? super K> cpr = comparator;
if (cpr != null) {//cpr就是我们的匿名内部类
do {
parent = t;
//匿名内部类方法
cmp = cpr.compare(key, t.key);//动态绑定我们的匿名内部类（对象）
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else//如果相等，即返回0，这个key就加入不了
return t.setValue(value);
} while (t != null);按长度排从小到大排
new TreeSet<>(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
return ((String)o1).length() - ((String) o2).length();
}
});TreeMap
调用put方法，第一次添加，把k-v封装到Entry对象，放入root
Entry<K,V> t = root;
if (t == null) {
//检查是不是null，并给比较器赋一个自己重写的比较器
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}第二次以及以上次数提交
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {//遍历所有的key，给当前key找到适当位置
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else//如果遍历过程中，发现准备添加Key和当前已有的Key相等就不添加
return t.setValue(value);
} while (t != null);
}