程序员人生 网站导航

java中的HashMap解析

栏目:php教程时间:2015-04-13 08:42:19

这篇文章准备从源码的角度带大家分析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; } }



------分隔线----------------------------
------分隔线----------------------------

最新技术推荐