java中的HashMap解析
來(lái)源：程序員人生 發(fā)布時(shí)間：2015-04-13 08:42:19 閱讀次數(shù)：4157次
這篇文章準(zhǔn)備從源碼的角度帶大家分析1下java中的hashMap的原理，在了解源碼之前，我們先根據(jù)自己的理解創(chuàng)建1個(gè)hashMap。
先說(shuō)明1下創(chuàng)建的具體原理是這樣的，所謂hashMap,必定是用hash方法來(lái)辨別不同的key值。學(xué)過(guò)hash的都知道，我們解決hash沖突的1種方法就是使用散列和桶，首先肯定所在的桶號(hào)，然后在桶里面逐一查找。其實(shí)我們也能夠單純使用數(shù)組實(shí)現(xiàn)map,使用散列是為了取得更高的查詢效力。
要寫(xiě)自己的hashmap前，必須說(shuō)明1下兩個(gè)方法，就是hashcode()和equals()方法，要在map里面判斷兩個(gè)key是不是相等，關(guān)鍵在于這個(gè)兩個(gè)函數(shù)的返回值1定要相等（只有1個(gè)相等是沒(méi)有用的，由于hashmap會(huì)先根據(jù)hashcode()方法查找桶，然后根據(jù)equals()方法獲得value）
如果我們沒(méi)有復(fù)寫(xiě)這個(gè)兩個(gè)方法，object類是根據(jù)類所在內(nèi)存地址來(lái)產(chǎn)生hashcode的，所以1般比較是不會(huì)相同的，又正由于這樣，我們?cè)谑褂米约簶?gòu)造的類當(dāng)key值的時(shí)候，有時(shí)是有必要復(fù)寫(xiě)這兩個(gè)方法的。下面是1個(gè)例子
class myClass{
int i = 0;
public myClass(int i) {
this.i = i;
}
@Override
public int hashCode() {
return i;
}
@Override
public boolean equals(Object obj) {
return obj instanceof myClass && i == ((myClass)obj).i;
}
}
注意上面的instanceof，我們首先要判斷參數(shù)的類是不是相同，這個(gè)非常重要，不過(guò)容易被疏忽。（由于有多是兩個(gè)不同的類，有相同的屬性，連屬性值都相同，這樣我們判斷就會(huì)失誤了）。另外我們要注意String類型重載了這兩個(gè)方法，所以兩個(gè)new String("aa")是相同的
在以下類中，我使用了1個(gè)arraylist來(lái)充當(dāng)鏈，首先我們來(lái)看1個(gè)鍵值對(duì)類，用來(lái)保存鍵和值，這個(gè)是1個(gè)內(nèi)部類，還有要實(shí)現(xiàn)hashmap必須先繼承1個(gè)AbstractMap<K,V>的抽象類
import java.util.AbstractMap;
import java.util.ArrayList;
import java.util.Map;
import java.util.Set;
public class MyHashMap<K, V> extends AbstractMap<K, V> {
//鏈表長(zhǎng)度
final static int SIZE = 999;
private List<K> keys = new ArrayList<K>();
private List<V> values = new ArrayList<V>();
/**
* Entry類，用于保存鍵值對(duì)
* @author Administrator
*
* @param <K>
* @param <V>
*/
static class MyEntry<K,V> implements Map.Entry<K, V>{
private K key;
private V value;
public MyEntry(K key,V value) {
this.key = key;
this.value = value;
}
@Override
public K getKey() {
return key;
}
@Override
public V getValue() {
return value;
}
@Override
public V setValue(V v) {
V oldValue = value;
value = v;
return oldValue;
}
@Override
public int hashCode() {
//使用key和value的hashcode共同構(gòu)造新的hashcode
return (key==null?0:key.hashCode())^(value==null?0:value.hashCode());
}
@Override
public boolean equals(Object obj) {
//注意要檢查類型是不是相同
if(!(obj instanceof MyEntry)) return false;
MyEntry en = (MyEntry)obj;
//注意空值的情況
return (key==null?en.getKey()==key:key.equals(en.getKey())) &&
(value==null?en.getKey()==value:value.equals(en.getValue()));
}
}
@SuppressWarnings("unchecked")
ArrayList<MyEntry<K,V>>[] buckets = new ArrayList[SIZE];
@Override
public Set<java.util.Map.Entry<K, V>> entrySet() {
// TODO Auto-generated method stub
return null;
}
}
對(duì)上面的鍵值對(duì)類MyEntry，我們要實(shí)現(xiàn)1個(gè)接口Map.Entry，由于我們1般使用hashmap都可以取得它的Entryset,繼承這個(gè)類正是為了這個(gè)做準(zhǔn)備
接下來(lái)我們先來(lái)實(shí)現(xiàn)put方法
/**
* put方法
*/
public V put(K key,V value){
//原值用于返回
V oldValue = null;
//避免越界
int index = Math.abs(key.hashCode())%SIZE;
//檢查是不是有桶，沒(méi)有創(chuàng)建1個(gè)
if(buckets[index]==null){
buckets[index] = new ArrayList<MyEntry<K,V>>();
}
ArrayList<MyEntry<K,V>> bucket = buckets[index];
//創(chuàng)建鍵值對(duì)對(duì)象entry
MyEntry<K, V> pair = new MyEntry<K, V>(key, value);
boolean found = false;
ListIterator<MyEntry<K, V>> it = bucket.listIterator();
//遍歷桶
while(it.hasNext()){
MyEntry<K, V> iPair = it.next();
//如果已在map里面，更新
if(iPair.getKey().equals(key)){
oldValue = iPair.getValue();
it.set(pair);
values.set(keys.indexOf(key),value);
found = true;
break;
}
}
//不在map里面，新增
if(!found){
keys.add(key);
values.add(value);
bucket.add(pair);
}
return oldValue;
}
這上面的思路應(yīng)當(dāng)說(shuō)是非常清晰，首先查找桶，沒(méi)有則新建，然后在桶里面查找key值，如果已存在map里面了，更新，否則新增。
再來(lái)看get方法，就更加清晰了
/**
* get方法
*/
public V get(Object key){
int index = Math.abs(key.hashCode())%SIZE;
if(buckets[index]==null) return null;
for(MyEntry<K, V> pair:buckets[index]){
if(pair.getKey().equals(key)){
return pair.getValue();
}
}
return null;
}
上面首先查找對(duì)應(yīng)桶，沒(méi)有返回null，如果有則在桶內(nèi)遍歷查找
最后再來(lái)看1下entrySet類
private class MyEntrySet extends AbstractSet<Map.Entry<K, V>>{
@Override
public Iterator<java.util.Map.Entry<K, V>> iterator() {
return new Iterator<java.util.Map.Entry<K, V>>() {
private int index = ⑴;
boolean canRemove;
@Override
public boolean hasNext() {
return index<keys.size()⑴;
}
@Override
public MyEntry<K, V> next() {
boolean canRemove = true;
++index;
return new MyEntry<K, V>(keys.get(index), values.get(index));
}
@Override
public void remove() {
if(!canRemove){
throw new IllegalStateException();
}
canRemove = false;
keys.remove(index);
values.remove(index--);
}
};
}
@Override
public int size() {
return keys.size();
}
}
這個(gè)內(nèi)部類主要是為我們提供entry用于外部遍歷使用
下面是完全代碼，大家可以測(cè)試1下
package test;
import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
import java.util.Set;
public class MyHashMap<K, V> extends AbstractMap<K, V> {
//鏈表長(zhǎng)度
final static int SIZE = 999;
private List<K> keys = new ArrayList<K>();
private List<V> values = new ArrayList<V>();
/**
* Entry類，用于保存鍵值對(duì)
* @author Administrator
*
* @param <K>
* @param <V>
*/
static class MyEntry<K,V> implements Map.Entry<K, V>{
private K key;
private V value;
public MyEntry(K key,V value) {
this.key = key;
this.value = value;
}
@Override
public K getKey() {
return key;
}
@Override
public V getValue() {
return value;
}
@Override
public V setValue(V v) {
V oldValue = value;
value = v;
return oldValue;
}
@Override
public int hashCode() {
//使用key和value的hashcode共同構(gòu)造新的hashcode
return (key==null?0:key.hashCode())^(value==null?0:value.hashCode());
}
@Override
public boolean equals(Object obj) {
//注意要檢查類型是不是相同
if(!(obj instanceof MyEntry)) return false;
MyEntry en = (MyEntry)obj;
//注意空值的情況
return (key==null?en.getKey()==key:key.equals(en.getKey())) &&
(value==null?en.getKey()==value:value.equals(en.getValue()));
}
}
@SuppressWarnings("unchecked")
ArrayList<MyEntry<K,V>>[] buckets = new ArrayList[SIZE];
/**
* put方法
*/
public V put(K key,V value){
//原值用于返回
V oldValue = null;
//避免越界
int index = Math.abs(key.hashCode())%SIZE;
//檢查是不是有桶，沒(méi)有創(chuàng)建1個(gè)
if(buckets[index]==null){
buckets[index] = new ArrayList<MyEntry<K,V>>();
}
ArrayList<MyEntry<K,V>> bucket = buckets[index];
//創(chuàng)建鍵值對(duì)對(duì)象entry
MyEntry<K, V> pair = new MyEntry<K, V>(key, value);
boolean found = false;
ListIterator<MyEntry<K, V>> it = bucket.listIterator();
//遍歷桶
while(it.hasNext()){
MyEntry<K, V> iPair = it.next();
//如果已在map里面，更新
if(iPair.getKey().equals(key)){
oldValue = iPair.getValue();
it.set(pair);
values.set(keys.indexOf(key),value);
found = true;
break;
}
}
//不在map里面，新增
if(!found){
keys.add(key);
values.add(value);
bucket.add(pair);
}
return oldValue;
}
/**
* get方法
*/
public V get(Object key){
int index = Math.abs(key.hashCode())%SIZE;
if(buckets[index]==null) return null;
for(MyEntry<K, V> pair:buckets[index]){
if(pair.getKey().equals(key)){
return pair.getValue();
}
}
return null;
}
private class MyEntrySet extends AbstractSet<Map.Entry<K, V>>{
@Override
public Iterator<java.util.Map.Entry<K, V>> iterator() {
return new Iterator<java.util.Map.Entry<K, V>>() {
private int index = ⑴;
boolean canRemove;
@Override
public boolean hasNext() {
return index<keys.size()⑴;
}
@Override
public MyEntry<K, V> next() {
boolean canRemove = true;
++index;
return new MyEntry<K, V>(keys.get(index), values.get(index));
}
@Override
public void remove() {
if(!canRemove){
throw new IllegalStateException();
}
canRemove = false;
keys.remove(index);
values.remove(index--);
}
};
}
@Override
public int size() {
return keys.size();
}
}
private MyEntrySet myEntrySet = new MyEntrySet();
@Override
public Set<java.util.Map.Entry<K, V>> entrySet() {
return myEntrySet;
}
}
OK，定義了我們自己hashmap以后，我們?cè)賮?lái)對(duì)比著看源代碼，就比較容易，雖然還有些區(qū)分，但是希望加深大家的理解
首先來(lái)看get方法
/**
* Returns the value of the mapping with the specified key.
*
* @param key
* the key.
* @return the value of the mapping with the specified key, or {@code null}
* if no mapping for the specified key is found.
*/
public V get(Object key) {
//檢查key為null
if (key == null) {
HashMapEntry<K, V> e = entryForNullKey;
return e == null ? null : e.value;
}
// Doug Lea's supplemental secondaryHash function (inlined)
//利用key的hashcode,計(jì)算新的hash
int hash = key.hashCode();
hash ^= (hash >>> 20) ^ (hash >>> 12);
hash ^= (hash >>> 7) ^ (hash >>> 4);
//遍歷數(shù)組查找是不是存在對(duì)應(yīng)值
HashMapEntry<K, V>[] tab = table;
for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
e != null; e = e.next) {
K eKey = e.key;
if (eKey == key || (e.hash == hash && key.equals(eKey))) {
return e.value;
}
}
return null;
}
用源代碼跟我們寫(xiě)的代碼比較，發(fā)現(xiàn)也是先處理null值，源碼中使用了1個(gè)特定的對(duì)象來(lái)代表key為Null的entry
然后是計(jì)算新的hash，這個(gè)怎樣計(jì)算我們不理它，只要知道為了hash更加完善，我們需要根據(jù)key的hashcode重新1次hash值
然后及時(shí)遍歷查找對(duì)應(yīng)value
接下來(lái)看put方法
/**
* Maps the specified key to the specified value.
*
* @param key
* the key.
* @param value
* the value.
* @return the value of any previous mapping with the specified key or
* {@code null} if there was no such mapping.
*/
@Override public V put(K key, V value) {
//如果新增的key為null,直接返回新生成的1個(gè)特定對(duì)象
if (key == null) {
return putValueForNullKey(value);
}
//重新計(jì)算hash值
int hash = secondaryHash(key.hashCode());
HashMapEntry<K, V>[] tab = table;
int index = hash & (tab.length - 1);
//遍歷，如果存在就更新
for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {
if (e.hash == hash && key.equals(e.key)) {
preModify(e);
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
// No entry for (non-null) key is present; create one
modCount++;
if (size++ > threshold) {
tab = doubleCapacity();
index = hash & (tab.length - 1);
}
//沒(méi)有就新增
addNewEntry(key, value, hash, index);
return null;
}
/**
*為控制生產(chǎn)1個(gè)特定對(duì)象
*/
private V putValueForNullKey(V value) {
HashMapEntry<K, V> entry = entryForNullKey;
if (entry == null) {
addNewEntryForNullKey(value);
size++;
modCount++;
return null;
} else {
preModify(entry);
V oldValue = entry.value;
entry.value = value;
return oldValue;
}
}
對(duì)照我們的代碼來(lái)看，思路差不多，就是處理null值的時(shí)候有不同
最后來(lái)看我們的entrySet
private final class EntrySet extends AbstractSet<Entry<K, V>> {
public Iterator<Entry<K, V>> iterator() {
return newEntryIterator();
}
public boolean contains(Object o) {
if (!(o instanceof Entry))
return false;
Entry<?, ?> e = (Entry<?, ?>) o;
return containsMapping(e.getKey(), e.getValue());
}
public boolean remove(Object o) {
if (!(o instanceof Entry))
return false;
Entry<?, ?> e = (Entry<?, ?>)o;
return removeMapping(e.getKey(), e.getValue());
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void clear() {
HashMap.this.clear();
}
}
必須實(shí)現(xiàn)的方法有對(duì)應(yīng)的實(shí)現(xiàn)，其中size是另外記錄的1個(gè)變量，用來(lái)記錄數(shù)據(jù)條數(shù)
這個(gè)必須結(jié)合iterator1起看，查找源代碼以后，發(fā)現(xiàn)對(duì)應(yīng)的是這個(gè)class
private final class EntryIterator extends HashIterator
implements Iterator<Entry<K, V>> {
public Entry<K, V> next() { return nextEntry(); }
}
繼承自HashIterator
private abstract class HashIterator {
int nextIndex;
HashMapEntry<K, V> nextEntry = entryForNullKey;
HashMapEntry<K, V> lastEntryReturned;
int expectedModCount = modCount;
HashIterator() {
if (nextEntry == null) {
HashMapEntry<K, V>[] tab = table;
HashMapEntry<K, V> next = null;
while (next == null && nextIndex < tab.length) {
next = tab[nextIndex++];
}
nextEntry = next;
}
}
public boolean hasNext() {
return nextEntry != null;
}
HashMapEntry<K, V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (nextEntry == null)
throw new NoSuchElementException();
HashMapEntry<K, V> entryToReturn = nextEntry;
HashMapEntry<K, V>[] tab = table;
HashMapEntry<K, V> next = entryToReturn.next;
while (next == null && nextIndex < tab.length) {
next = tab[nextIndex++];
}
nextEntry = next;
return lastEntryReturned = entryToReturn;
}
public void remove() {
if (lastEntryReturned == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
HashMap.this.remove(lastEntryReturned.key);
lastEntryReturned = null;
expectedModCount = modCount;
}
}
生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
