java中的HashMap解析

这篇文章准备从源码的角度带大家分析1下java中的hashMap的原理,在了解源码之前,我们先根据自己的理解创建1个hashMap。

先说明1下创建的具体原理是这样的,所谓hashMap,必定是用hash方法来辨别不同的key值。学过hash的都知道,我们解决hash冲突的1种方法就是使用散列和桶,首先肯定所在的桶号,然后在桶里面逐一查找。其实我们也能够单纯使用数组实现map,使用散列是为了取得更高的查询效力。

要写自己的hashmap前,必须说明1下两个方法,就是hashcode()和equals()方法,要在map里面判断两个key是不是相等,关键在于这个两个函数的返回值1定要相等(只有1个相等是没有用的,由于hashmap会先根据hashcode()方法查找桶,然后根据equals()方法获得value)

如果我们没有复写这个两个方法,object类是根据类所在内存地址来产生hashcode的,所以1般比较是不会相同的,又正由于这样,我们在使用自己构造的类当key值的时候,有时是有必要复写这两个方法的。下面是1个例子

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,我们首先要判断参数的类是不是相同,这个非常重要,不过容易被疏忽。(由于有多是两个不同的类,有相同的属性,连属性值都相同,这样我们判断就会失误了)。另外我们要注意String类型重载了这两个方法,所以两个new String("aa")是相同的

在以下类中,我使用了1个arraylist来充当链,首先我们来看1个键值对类,用来保存键和值,这个是1个内部类,还有要实现hashmap必须先继承1个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> {
//链表长度
final static int SIZE = 999;
private List<K> keys = new ArrayList<K>();
    private List<V> values = new ArrayList<V>();
 /**
* Entry类,用于保存键值对
* @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共同构造新的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;
}

}

对上面的键值对类MyEntry,我们要实现1个接口Map.Entry,由于我们1般使用hashmap都可以取得它的Entryset,继承这个类正是为了这个做准备

接下来我们先来实现put方法

/**
     * put方法
     */
    public V put(K key,V value){
        //原值用于返回
        V oldValue = null;
        //避免越界
        int index = Math.abs(key.hashCode())%SIZE;
        //检查是不是有桶,没有创建1个
        if(buckets[index]==null){
            buckets[index] = new ArrayList<MyEntry<K,V>>();
        }
        ArrayList<MyEntry<K,V>> bucket = buckets[index];
        //创建键值对对象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;
    }

这上面的思路应当说是非常清晰,首先查找桶,没有则新建,然后在桶里面查找key值,如果已存在map里面了,更新,否则新增。

再来看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;
}

上面首先查找对应桶,没有返回null,如果有则在桶内遍历查找

最后再来看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();
        }        
    }

这个内部类主要是为我们提供entry用于外部遍历使用

下面是完全代码,大家可以测试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> {
    //链表长度
    final static int SIZE = 999;
    private List<K> keys = new ArrayList<K>();
    private List<V> values = new ArrayList<V>();
    
    /**
     * Entry类,用于保存键值对
     * @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共同构造新的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;
        //检查是不是有桶,没有创建1个
        if(buckets[index]==null){
            buckets[index] = new ArrayList<MyEntry<K,V>>();
        }
        ArrayList<MyEntry<K,V>> bucket = buckets[index];
        //创建键值对对象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以后,我们再来对比着看源代码,就比较容易,虽然还有些区分,但是希望加深大家的理解

首先来看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,计算新的hash
 int hash = key.hashCode();
hash ^= (hash >>> 20) ^ (hash >>> 12);
hash ^= (hash >>> 7) ^ (hash >>> 4);
//遍历数组查找是不是存在对应值
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;
}

用源代码跟我们写的代码比较,发现也是先处理null值,源码中使用了1个特定的对象来代表key为Null的entry

然后是计算新的hash,这个怎样计算我们不理它,只要知道为了hash更加完善,我们需要根据key的hashcode重新1次hash值

然后及时遍历查找对应value

接下来看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个特定对象
 if (key == null) {
return putValueForNullKey(value);
}
//重新计算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);
}
//没有就新增
 addNewEntry(key, value, hash, index);
return null;
}
/**
*为控制生产1个特定对象
*/
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;
        }
    }

对照我们的代码来看,思路差不多,就是处理null值的时候有不同
最后来看我们的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();
}
}

必须实现的方法有对应的实现,其中size是另外记录的1个变量,用来记录数据条数

这个必须结合iterator1起看,查找源代码以后,发现对应的是这个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;
}
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » java中的HashMap解析

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡