本文共 2318 字，大约阅读时间需要 7 分钟。

说起HashMap的强大之处，就是其内部使用了哈希算法和链表算法，充分利用好加载因子的强大推动，使得在时间和空间上的成本寻求一种折中，其内部元素在存储和提取不仅可以充分利用好HashMap初始化的空间，而且查询效率及其的高！

在面试中，面试官会常问HashMap的底层源码的实现，接下来我简单的手动实现一个HashMap集合：

（一）HashMap中存储的元素类型即为键值对存在，定义一个能包含键值对的内部类：

class MapEntry {	Object key;	Object value;	public MapEntry(Object key, Object value) {		super();		this.key = key;		this.value = value;	}}

（二）我们使用java.util.LinkedList双向链表来模拟HashMap中底层实现的数组（即链表数组）

/** * 1.提高查询的效率 2.默认加载因子 (0.75) 即在时间和空间成本上寻求一种折衷。加载因子过大存储空间能得到充分利用，但查询效率会低一点； * 加载因子过小，存储空间利用率降低，但是查询速度会高一点！(加载因子的设计大小要保证存储空间充分利用，且查询效率高) */public class ManualHashMap {	LinkedList[] arr = new LinkedList[999]; // 键值对集合！ Map底层结构是:数组 + 链表	int size = 0; // HashMap的容量	// 构造方法	public ManualHashMap() {	}	/*	 * 向HashMap中存入键值对	 */	public void put(Object key, Object value) {		MapEntry node = new MapEntry(key, value);		/*		 * 获取该键值对在数组中的索引位置(0~998);		 * 重写HashCode()方法就是为了让具有相同属性对象具有相同的HashCode值(地址码);		 * 由于重写HashCode()方法在任何种程度上，都会出现一定的Bug，使得具有不同属性值都会有相同的HashCode码值；		 * 此时就需要重写equals()方法，进行二次比较key值是否相同，就可做到万无一失了！		 */		int hash = node.key.hashCode() % arr.length;		hash = hash < 0 ? -hash : hash;		if (arr[hash] == null) { // 此索引位置为空			LinkedList
   
     list = new LinkedList<>();	//创建一个双向链表			arr[hash] = list;			list.add(node);			size++;		} else { // 该位置有元素			LinkedList
    
      list = arr[hash]; // 取出该索引处的链表			// 判断有没有键值重复			boolean flag = false;	//判断此链表中，是否存在重复的键值			for (int i = 0; i < list.size(); i++) {				MapEntry temp = (MapEntry) list.get(i);				if (temp.key.equals(key)) { // 键值有重复					temp.value = value; // value值覆盖					flag = true;				}			}			if(!flag){	//不存在重复的key，需添加此元素				list.add(node);				size++;			}		}	}	/*	 * 获取键值对中某个键值对对象	 */	public Object get(Object key) {		int hash = key.hashCode() % arr.length;		hash = hash < 0 ? -hash : hash;		if (arr[hash] != null) {			LinkedList
     
       list = arr[hash];			for (int i = 0; i < list.size(); i++) {				MapEntry temp = (MapEntry) list.get(i);				if(temp.key.equals(key)){					return temp.value;				}			}		}		return null;	}	public static void main(String[] args) {		ManualHashMap map = new ManualHashMap();		map.put("6", "b");		map.put("6", "a");		map.put("5", "c");		map.put("4", "d");		System.out.println(map.size);	//3		System.out.println(map.get("6"));	//a	}}
     
    
   

转载地址：http://zcxxi.baihongyu.com/