看看HashMap对应的源码。
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
克隆和序列化不懂，先看Map。
public interface Map<K,V> {
//这些方法就不用写注释了吧，一看就懂。
int size();
boolean isEmpty();
boolean containsKey(Object key);
boolean containsValue(Object value);
V get(Object key);
V put(K key, V value);
V remove(Object key);
void putAll(Map<? extends K, ? extends V> m);
void clear();
//这里是返回的不重复的集合
Set<K> keySet();
//这里返回的是一个集合
Collection<V> values();
Set<Map.Entry<K, V>> entrySet();
boolean equals(Object o);
int hashCode();
//还有一个内部的接口，这个相当于一个key-value数据。
interface Entry<K,V> {
K getKey();
V getValue();
V setValue(V value);
boolean equals(Object o);
int hashCode();
}
}
这个方法有700行，我就挑出几个说一说
public abstract class AbstractMap<K,V> implements Map<K,V> {
protected AbstractMap() {
}
}
简单介绍几个，都没什么实际意思。
//声明了抽象变量，里面直接是Map的内部类，这个Set包含着所有的数据key+value
public abstract Set<Entry<K,V>> entrySet();
//Map长度
public int size() {
return entrySet().size();
}
//是否为空
public boolean isEmpty() {
return size() == 0;
}
//是否包含某个值
public boolean containsValue(Object value) {
//要查找出是否包含，于是开始遍历这个Set。
//这里可以使用 for each，但是这个方法写于jdk1.2，所以当时还没有。遍历的过程很简单。
Iterator<Entry<K,V>> i = entrySet().iterator();
//这里还有一个判空。
if (value==null) {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (e.getValue()==null)
return true;
}
} else {
while (i.hasNext()) {
Entry<K,V> e = i.next();
//注意：比较用的是equals，而不是==
if (value.equals(e.getValue()))
return true;
}
}
return false;
}
//查找这个值，一样遍历Set
public V get(Object key) {
Iterator<Entry<K,V>> i = entrySet().iterator();
if (key==null) {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (e.getKey()==null)
return e.getValue();
}
} else {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (key.equals(e.getKey()))
return e.getValue();
}
}
return null;
}
//这个方法是要求重写的。
public V put(K key, V value) {
throw new UnsupportedOperationException();
}
//删除某个键值对
public V remove(Object key) {
Iterator<Entry<K,V>> i = entrySet().iterator();
Entry<K,V> correctEntry = null;
//key值可以为null，查出相应key值所对应的键值对。
if (key==null) {
while (correctEntry==null && i.hasNext()) {
Entry<K,V> e = i.next();
if (e.getKey()==null)
correctEntry = e;
}
} else {
while (correctEntry==null && i.hasNext()) {
Entry<K,V> e = i.next();
if (key.equals(e.getKey()))
correctEntry = e;
}
}
//这里开始caozuo.html" target="_blank">删除操作
V oldValue = null;
if (correctEntry !=null) {
oldValue = correctEntry.getValue();
//用迭代器的删除方法。
i.remove();
}
//返回删除的value。
return oldValue;
}
//添加一个Map操作，直接循环添加
public void putAll(Map<? extends K, ? extends V> m) {
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}
//直接使用了set的clear方法
public void clear() {
entrySet().clear();
}
AbstractMap就看到这里，毕竟主要是看HashMap。
HashMap首先会开辟一个16空间的Entry（键值对）数组，
Entry类中包括
final K key; V value; Entry<K,V> next; final int hash;?
然后对存入的key进行hash运算，算到一个数字（1-15），存入对应位置。
如果对应位置一有数据，则替代当前数据，然后将原数据的引用给新数据，即赋值给next。当存到一定的值后，会扩展空间。
查询的时候将key进行计算得到（1-15），然后查询对应位置，一直去next，知道取到数据或结束。
public HashMap() {
//一个倍数 0.75f
this.loadFactor = DEFAULT_LOAD_FACTOR;
//临界值 16*0.75=12，表示存了12个值以后要开辟新的空间
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
//初始空间16
table = new Entry[DEFAULT_INITIAL_CAPACITY];
//init里面没有内容。
init();
}
public V put(K key, V value) {
//如果key为空，单独做插入操作。
if (key == null)
//插入key为null的值，返回之前此处的值。
return putForNullKey(value);
//计算hash值，下面的两个方法
int hash = hash(key.hashCode());
//根据hash值获得在数组中的位置
int i = indexFor(hash, table.length);
//循环位置。直到为空位置
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//如果包含key值和hash值都相等。
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
//将原有的键值对的value值替换。
V oldValue = e.value;
e.value = value;
//这是替换要执行的方法，现在内部还没有处理。
e.recordAccess(this);
//将就得value返回。
return oldValue;
}
}
//这里代表这个key值要新加入这个map。
//修改次数
?modCount++;
//加入
addEntry(hash, key, value, i);
return null;
}
//添加一个空的key。添加到数组的0位置。
private V putForNullKey(V value) {
//判断对应位置时候为空，
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
//对应key值不为空
if (e.key == null) {
//更新数据。
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
//返回被替换掉的值。
return oldValue;
}
}
modCount++;
//添加一个0位置的。
addEntry(0, null, value, 0);
return null;
}
//添加一个键值对，传入对应hash值和数组位置。
void addEntry(int hash, K key, V value, int bucketIndex) {
//将这个位置的原有值取出来，
Entry<K,V> e = table[bucketIndex];
//新建一个，传入hash值，还有它的下一个键值对。所以同一个位置，后面插入的数据会查询快一点点。
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
//如果size大于临界值。
if (size++ >= threshold)
//将原来空间扩大为两倍
resize(2 * table.length);
}
//开辟新空间
void resize(int newCapacity) {
Entry[] oldTable = table;
//旧数组的长度
int oldCapacity = oldTable.length;
//最大空间数。
if (oldCapacity == MAXIMUM_CAPACITY) {
//边界值为int的最大值。
threshold = Integer.MAX_VALUE;
//结束。
return;
}
//新建一个数组,大小为传入的数字。
Entry[] newTable = new Entry[newCapacity];
//转移新数组
transfer(newTable);
//给table赋值。
table = newTable;
//边界值更新。
threshold = (int)(newCapacity * loadFactor);
}
//将数据全部重新插入新数组，规则使用新得数组空间值计算。
void transfer(Entry[] newTable) {
//这里用的是旧数组。
Entry[] src = table;
int newCapacity = newTable.length;
//遍历旧的数组，
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
//为空的键值对不用另外做处理
if (e != null) {
src[j] = null;
do {
Entry<K,V> next = e.next;
//根据hash值获取对应数组位置。
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
//获取key值对应信息。
public V get(Object key) {
//key为null时候
if (key == null)
//直接从0号位置开始查。
return getForNullKey();
//计算key值对应hash。
int hash = hash(key.hashCode());
//使用indexFor计算出对应table的位置，然后开始遍历。直到找到或者结束。
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
//获取key值为null的value。
private V getForNullKey() {
//先查找0号位，然后依次找next，直到找到key为null的值或键值对为空，返回。
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
将key进行hash计算，然后找到键值对，然后返回结果
遍历数组，知道找到value。很费性能。
遍历数组，全部置为null。
找出对应key，去掉，更新关联值。
?
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) {
return h & (length-1);
}
计算都是通过hashCode来计算，所以存入HashMap的对象最好不要将hashCode写成一个值。hashCode各个类都有自己的生成方法，似乎Object默认的是内存位置，但是刚刚观察Integer和String都覆写了的。
int占32位，无符号左移20位，空位补0，无符号右移20位。算了，这个二进制运算符要系统的看，先这样把。
看到这里都差不多了，主要是理解HashMap的结构和hash算法。
同时产生了两个疑问，先记下来。
疑问一：只实现抽象类AbstractMap不行么？为什么还要implements Map ，不重复吗？
疑问二：transient volatile 这样声明变量是为什么？
?
相关文章
