爱威尔-java HashMap入门-抛砖引玉

这个话题还是要从面试说起，说实话我这个人就是非常不擅长面试，对基础掌握的也不是对答如流，而且jdk集合的底层原理一直处于懵懵懂懂的状态，这么说如果要我去写偏底层的中间件那基础肯定要恶补一下，如果不设计多线程和偏底层的开发工作说实话你从来不会想起来看看jdk底层的东西，我也是这种感受。 
 那我们就从hashmap说起，这可能是面试问到最多的地方之一了，最新的jdk1.8版本hashmap有两千多行代码，感觉没人知道这分析阅读还真是个难事，想通俗易懂的一两句话说清楚也没那么容易，那今天就粗浅的认识一下，也算是抛砖引玉吧（其实我也知道的不多） 
 
 我们现在从map这个接口开始，翻看源码发现： 
<img src="85/20171128102141_233.png" alt=""> 
 
 
 接口里面套接口，这里我就不啰嗦了，但是对于我们来说就要问个为什么，有什么好处，想解决什么问题，能带来什么好处。 
 如果我自己写一个hashmap，接口怎么写： 
<pre class="prettyprint lang-java">public interface MyMap<K,V> {

V put(K key,V value);
	
	V get(K key);
	
	int size();
	
	interface Entry<K,V>{
		K getKey();
		V getValue();
	}
}
</pre> 
 来个简化版的，这个代码我想理解起来应该没问题，我都不用解释。 
   
 接下来就是实现： 
<pre class="prettyprint lang-java">public class MyHashMap<K,V> implements MyMap<K, V> {

}
</pre> 
 我写这么一点大家应该还是能理解的： 
 private static Integer defaultLength = 16; 
 就是：static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 
   
 private static double defaultLoadFactor = 0.75; 
 就是：static final float DEFAULT_LOAD_FACTOR = 0.75f; 
   
 table = new Entry[defaultLength]; 
 这个我们知道这里的数组里面存放的其实是Entry，我们把它理解成对象里面存放Key和Value。 
   
 接下来看这段代码： 
 
<pre class="prettyprint lang-java">class Entry<K,V> implements MyMap.Entry<K, V>{

K key;
		V value;
		Entry<K,V> next;
		int index;

Entry(K key, V value, Entry<K, V> next, int index) {
			super();
			this.key = key;
			this.value = value;
			this.next = next;
			this.index = index;
		}

@Override
		public K getKey() {
			return key;
		}

@Override
		public V getValue() {
			return value;
		}
		
	}
</pre> 
 我们在内置一个Entry的实现，也就是实现里面嵌套实现。 
   
 看看这个：Entry<K,V> next;  什么意思？这段代码里面最重要的就这个了，存放对象的下一个对象，什么意思？如果你知道链表这个概念的话你就容易理解了，什么叫做链，抛开技术层面你也应该从现实生活理解他。 
   
 看到这里你对HashMap还没有认知么？我想应该有了，应对一般的面试应该没问题了，不就是一个数组，数组里面存放的是一个K，V的对象，而且对象还可以包含下一个与他挨着的对象，至于为什么对象与对象会像链表一样串在一起，我这里先提个醒就是因为hash（哈希），今天不讨论这个问题，自己有时间慢慢理解，可以这么说hash在计算机应用程序领域应用非常广泛。 
   
 到现在我么还没有对我们这个hashmap做CRUD，既然上面提到了hash那我们也要做一个hash，而且是这么重要的概念： 
<pre class="prettyprint lang-java">private int getIndex(K key) {
		//取模运算
		int m = this.defaultLength - 1;
		return key.hashCode() % m;
	}
</pre> 
 够简单吧，就是这么简单的hash，但是key.hashCode()，点进去看源码：public native int hashCode(); 
 不好意思没有源码可以看（openjava我没有看过不知道能不能看），意思就是他回去调用操作系统底层去计算，看到了吧java在获取hashCode()的时候竟然要依赖各个操作系统，再次说明了基础是多么的重要。 
   
 拿到了hash’值下面的操作就不难了，先看get方法： 
<pre class="prettyprint lang-java">@Override
	public V get(K key) {
		//1.通过hash函数获取index下标
		int index = getIndex(key);
		return table[index] == null ? null : table[index].getValue();
	}
</pre> 
 不用解释吧。 
   
 再看put方法： 
<pre class="prettyprint lang-java">@Override
	public V put(K key, V value) {
		//1.通过hash函数获取index下标
		int index = getIndex(key);
		//2.判断该下标是否有值
		Entry<K,V> entry = table[index];
		if (null == entry) {
			table[index] = new Entry(key,value,null,index);
			size++;
		}else {
			table[index] = new Entry<K, V>(key, value, entry, index);
			entry = table[index];
		}
		
		return table[index].getValue();
	}
</pre> 
 我感觉也没什么可解释的。就这样简单的hashmap就写好了，这里不给大家将一些难以理解的专业术语，大家可以在此基础上去理解jdk 的hashmap，我想会有不同的收获。 
<pre class="prettyprint lang-java">package springbootdubbo.rocketmqTest;

public class MyHashMap<K,V> implements MyMap<K, V> {

private static Integer defaultLength = 16;
	private static double defaultLoadFactor = 0.75;
	
	private Entry<K,V>[] table = null;
	//数组元素个数
	private int size = 0;
	
	MyHashMap(int defaultLength,double defaultLoadFactor) {
		this.defaultLength = defaultLength;
		this.defaultLoadFactor = defaultLoadFactor;
		
		table = new Entry[defaultLength];
	}
	MyHashMap() {
		this(defaultLength, defaultLoadFactor);
	}
	
	@Override
	public V put(K key, V value) {
		//1.通过hash函数获取index下标
		int index = getIndex(key);
		//2.判断该下标是否有值
		Entry<K,V> entry = table[index];
		if (null == entry) {
			table[index] = new Entry(key,value,null,index);
			size++;
		}else {
			table[index] = new Entry<K, V>(key, value, entry, index);
			entry = table[index];
		}
		
		return table[index].getValue();
	}
	
	private int getIndex(K key) {
		//取模运算
		int m = this.defaultLength - 1;
		return key.hashCode() % m;
	}

@Override
	public V get(K key) {
		//1.通过hash函数获取index下标
		int index = getIndex(key);
		return table[index] == null ? null : table[index].getValue();
	}

@Override
	public int size() {
		return size;
	}

class Entry<K,V> implements MyMap.Entry<K, V>{

K key;
		V value;
		Entry<K,V> next;
		int index;

Entry(K key, V value, Entry<K, V> next, int index) {
			super();
			this.key = key;
			this.value = value;
			this.next = next;
			this.index = index;
		}

@Override
		public K getKey() {
			return key;
		}

@Override
		public V getValue() {
			return value;
		}
		
	}
}
</pre> 测试自己来吧！<a href="http://www.iteye.com/topic/539465">主题：深入理解HashMap</a>