java中的HashMap解析

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

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

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

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

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")是相同的

在以下类中,我使用了一个arraylist来充当链,首先我们来看一个键值对类,用来保存键和值,这个是一个内部类,还有要实现hashmap必须先继承一个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,我们要实现一个接口Map.Entry,因为我们一般使用hashmap都可以获得它的Entryset,继承这个类正是为了这个做准备

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

/**
     * put方法
     */
    public V put(K key,V value){
        //原值用于返回
        V oldValue = null;
        //防止越界
        int index = Math.abs(key.hashCode())%SIZE;
        //检查是否有桶,没有创建一个
        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,如果有则在桶内遍历查找

最后再来看一下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 = -1;
                boolean canRemove;
                @Override
                public boolean hasNext() {
                    return index<keys.size()-1;                    
                }

                @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用于外部遍历使用

下面是完整代码,大家可以测试一下

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;
        //检查是否有桶,没有创建一个
        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 = -1;
                boolean canRemove;
                @Override
                public boolean hasNext() {
                    return index<keys.size()-1;                    
                }

                @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值,源码中使用了一个特定的对象来代表key为Null的entry

然后是计算新的hash,这个怎么计算我们不理它,只要知道为了hash更加完美,我们需要根据key的hashcode重新一次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,直接返回新生成的一个特定对象
        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;
    }
    /**
    *为控制生产一个特定对象
    */
    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是另外记录的一个变量,用来记录数据条数

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

java中的HashMap解析的相关文章

转:在java中使用dom4j解析xml

在java中使用dom4j解析xml 虽然Java中已经有了Dom和Sax这两种标准解析方式 但其操作起来并不轻松,对于我这么一个初学者来说,其中部分代码是活生生的恶心 为此,伟大的第三方开发组开发出了Jdom和Dom4j等工具 鉴于目前的趋势,我们这里来讲讲Dom4j的基本用法,不涉及递归等复杂操作 Dom4j的用法很多,官网上的示例有那么点儿晦涩,这里就不写了 首先我们需要出创建一个xml文档,然后才能对其解析 xml文档: <?xml version="1.0" encod

Java中构造和解析JSON

什么是 Json? JSON(JvaScript Object Notation)(官网网站:http://www.json.org/)是 一种轻量级的数据交换格式.  易于人阅读和编写.同时也易于机器解析和生成.它基于 JavaScript Programming Language, Standard ECMA-262 3rd Edition - December 1999 的一个子集.  JSON 采用完全独立于语言的文本格式,但是也使用了类似于 C 语言家族的习惯(包括C, C++, C#

深入理解Java中的HashMap

HashMap继承自抽象类AbstractMap,抽象类AbstractMap实现了Map接口.关系图如下所示: import java.util.*; public class SimpleMap<K,V> extends AbstractMap<K,V> { //keys存储所有的键 private List<K> keys = new ArrayList<K>(); //values存储所有的值 private List<V> values

java中static关键字解析

static关键字是很多朋友在编写代码和阅读代码时碰到的比较难以理解的一个关键字,也是各大公司的面试官喜欢在面试时问到的知识点之一.下面就先讲述一下static关键字的用法和平常容易误解的地方,最后列举了一些面试笔试中常见的关于static的考题.以下是本文的目录大纲: 一.static关键字的用途 二.static关键字的误区 三.常见的笔试面试题 若有不正之处,希望谅解并欢迎批评指正. 请尊重作者劳动成果,转载请标明原文链接: http://www.cnblogs.com/dolphin05

浅析java中的hashMap

?  HashMap 和 HashSet 是 Java Collection Framework 的两个重要成员,其中 HashMap 是 Map 接口的常用实现类,HashSet 是 Set 接口的常用实现类.虽然 HashMap 和 HashSet 实现的接口规范不同,但它们底层的 Hash 存储机制完全一样,甚至 HashSet 本身就采用 HashMap 来实现的. 通过 HashMap.HashSet 的源代码分析其 Hash 存储机制集合和引用 就像引用类型的数组一样,当我们把 Ja

Java中的HashMap和HashTable到底哪不同?

学习Java的同学注意了!!! 学习过程中遇到什么问题或者想获取学习资源的话,欢迎加入Java学习交流群,群号码:456544752  我们一起学Java! HashMap和HashTable有什么不同?在面试和被面试的过程中,我问过也被问过这个问题,也见过了不少回答,今天决定写一写自己心目中的理想答案. 代码版本 JDK每一版本都在改进.本文讨论的HashMap和HashTable基于JDK 1.7.0_67.源码见这里 1. 时间 HashTable产生于JDK 1.1,而HashMap产生

[非原创]java 中static作用解析

static表示“全局”或者“静态”的意思,用来修饰成员变量和成员方法,也可以形成静态static代码块,但是Java语言中没有全局变量的概念. 被static修饰的成员变量和成员方法独立于该类的任何对象.也就是说,它不依赖类特定的实例,被类的所有实例共享.只要这个类被加载,Java虚拟 机就能根据类名在运行时数据区的方法区内定找到他们.因此,static对象可以在它的任何对象创建之前访问,无需引用任何对象. 用public修饰的static成员变量和成员方法本质是全局变量和全局方法,当声明它类

Java中的HashMap和HashTable

对于 Map ,最直观就是理解就是键值对,映射,key-value 形式.一个映射不能包含重复的键,一个键只能有一个值.平常我们使用的时候,最常用的无非就是 HashMap. HashMap 实现了 Map 接口,允许使用 null 值 和 null 键,并且不保证映射顺序. HashMap 有两个参数影响性能: 初始容量:表示哈希表在其容量自动增加之前可以达到多满的一种尺度加载因子:当哈希表中的条目超过了容量和加载因子的乘积的时候,就会进行重哈希操作.如下成员变量源码: 1 static fi

java中对HashMap遍历的方式

第一种是利用HashMap的entrySet()方法: Map<String,String> map = new HashMap<String,String>(); Iterator iter = map.entrySet().iterator(); while (iter.hasNext()) { Map.Entry entry = (Map.Entry) iter.next(); String key = entry.getKey(); String val = entry.g