HashMap集合是Map接口的实现类，在Map集合不同于Collectiion集合，Map集合存放的是键值对，通过键(key)可以找到对应的值（value），而且每一个key是唯一的。那么该如何自定义实现HashMap呢？
通过阅读jdk的源代码，发现HashMap的底层数据结构其实就是数组加上链表。笔者通过阅读源码，自定义实现了HashMap。
数组里面存放的是链表LinkedList，而链表里存放的是Entry(表示一对键值对)。首先通过key的hash值计算一个出一个数值，把它当做数组的索引(index)，如果有两个key计算得到的index相同，则这两对键值对存放在索引为index的LinkedList当中。如果两个key计算得到的index不同，这这两个键值对会存放在不同的LinkedList当中。如图：
具体的代码实现如下：
package com.tiantang.collection;
/**
* 自定义的Map集合接口
* @author LiuJinkun
*
*/
public interface MyMap {
/**
* 返回集合的大小
* @return
*/
int size();
/**
* 存放键值对
* @param key
* @param value
*/
void put(Object key,Object value);
/**
* 根据键查找值
* @param key
* @return
*/
Object get(Object key);
/**
* 判断集合是否为空
* @return
*/
boolean isEmpty();
/**
* 移除键所对应的键值对
* @param key
*/
void remove(Object key);
/**
* 集合中是否包含指定的key
* @param key
* @return
*/
boolean containsKey(Object key);
/**
* 集合中是否包含指定的value值
* @param value
* @return
*/
boolean containsValue(Object value);
}
package com.tiantang.collection;
import java.util.LinkedList;
/**
* 自定义的HashMap
*
* @author LiuJinkun
*
*/
public class MyHashMap implements MyMap {
private int size;
// 用来存放LinkedList的数组（数组的下标用key所对应的hash值进行相应的计算而得到）
private LinkedList<Entry>[] arr;
/**
* 无参构造器，默认初始化数组容量为16 事实上，这里数组的初始化大小只要求大于0即可，但过大会占用太多的内存，过小则会影响查询的性能
* 因此这里根据参照源码，使其初始化大小为16（jdk源码根据负载均衡量会重新该表数组的大小，这里笔者简单的实现，没有考虑那么详细）
*/
public MyHashMap() {
// 默认初始化数组容量为16
this(16);
}
/**
* 有参构造器
*
* @param initialCapacity
*/
public MyHashMap(int initialCapacity) {
if (initialCapacity <= 0) {
throw new IllegalArgumentException();
} else {
this.arr = new LinkedList[initialCapacity];
}
}
@Override
public int size() {
return size;
}
@Override
public void put(Object key, Object value) {
Entry entry = new Entry(key, value);
int index = getIndex(key);
if (arr[index] == null) {
LinkedList<Entry> list = new LinkedList<Entry>();
list.add(entry);
arr[index] = list;
size++;
} else {
// 然后判断key是否重复
for (int i = 0; i < arr[index].size(); i++) {
//如果与集合中的key重复的就替换掉原来的value值
if (arr[index].get(i).getKey().equals(key)) {
arr[index].get(i).value=value;
return;
}
}
//如果不重复，就添加
arr[index].add(entry);
size++;
}
}
@Override
public Object get(Object key) {
int index = getIndex(key);
//获得该索引处存放的链表
LinkedList<Entry> list=arr[index];
if(list!=null){
//遍历链表，若果key相等就返回对应的value
for(int i=0;i<list.size();i++){
if(list.get(i).key.equals(key)){
return list.get(i).value;
}
}
}
return null;
}
@Override
public boolean isEmpty() {
return size==0;
}
@Override
public void remove(Object key) {
int index = getIndex(key);
LinkedList<Entry> list=arr[index];
if(list!=null){
for(int i=0;i<list.size();i++){
if(list.get(i).key.equals(key)){
list.remove(i);
size--;
return;
}
}
}
}
@Override
public boolean containsKey(Object key) {
//根据key得到索引
int index = getIndex(key);
LinkedList<Entry> list=arr[index];
if(list!=null){
for(int i=0;i<list.size();i++){
if(list.get(i).key.equals(key)){
return true;
}
}
}
return false;
}
/**
* 根据key的hash值然后通过计算得到数组索引
* 算法为：hash值除以arr数组的长度（这样保证了得到的数组索引是有效的）
* @param key
* @return
*/
private int getIndex(Object key) {
int index=key.hashCode()%arr.length;
return index;
}
@Override
public boolean containsValue(Object value) {
for(int i=0;i<arr.length;i++){
if(arr[i]!=null){
for(int j=0;j<arr[i].size();j++){
if(arr[i].get(j).value.equals(value)){
return true;
}
}
}
}
return false;
}
private class Entry {
Object key;
Object value;
public Object getKey() {
return key;
}
public Object getValue() {
return value;
}
public Entry(Object key, Object value) {
this.key = key;
this.value = value;
}
}
}
上述代码只是简单实现了Map里面的部分方法，而且代码还可以在很大程度上优化，读者如果有兴趣可以自行研究。
下面是笔者又优化了部分代码后的结果：
package com.tiantang.collection;
import java.util.LinkedList;
/**
* 自定义的HashMap
*
* @author LiuJinkun
*
*/
public class MyHashMap implements MyMap {
private int size;
// 用来存放LinkedList的数组（数组的下标用key所对应的hash值进行相应的计算而得到）
private LinkedList<Entry>[] arr;
/**
* 无参构造器，默认初始化数组容量为16 事实上，这里数组的初始化大小只要求大于0即可，但过大会占用太多的内存，过小则会影响查询的性能
* 因此这里根据参照源码，使其初始化大小为16（jdk源码根据负载均衡量会重新该表数组的大小，这里笔者简单的实现，没有考虑那么详细）
*/
public MyHashMap() {
// 默认初始化数组容量为16
this(16);
}
/**
* 有参构造器
*
* @param initialCapacity
*/
public MyHashMap(int initialCapacity) {
if (initialCapacity <= 0) {
throw new IllegalArgumentException();
} else {
this.arr = new LinkedList[initialCapacity];
}
}
@Override
public int size() {
return size;
}
@Override
public void put(Object key, Object value) {
Entry entry = new Entry(key, value);
int index = getIndex(key);
if (arr[index] == null) {
LinkedList<Entry> list = new LinkedList<Entry>();
list.add(entry);
arr[index] = list;
size++;
} else {
// 然后判断key是否重复
for (int i = 0; i < arr[index].size(); i++) {
//如果与集合中的key重复的就替换掉原来的value值
if (arr[index].get(i).getKey().equals(key)) {
arr[index].get(i).value=value;
return;
}
}
//如果不重复，就添加
arr[index].add(entry);
size++;
}
}
@Override
public Object get(Object key) {
int index = getIndex(key);
//获得该索引处存放的链表
LinkedList<Entry> list=arr[index];
int i=getIndexOfNode(key, list);
if(i!=-1){
return list.get(i).value;
}
return null;
}
@Override
public boolean isEmpty() {
return size==0;
}
@Override
public void remove(Object key) {
int index = getIndex(key);
LinkedList<Entry> list=arr[index];
int i=getIndexOfNode(key, list);
if(i!=-1){
list.remove(i);
}
}
/**
* 根据key的hash值然后通过计算得到数组索引
* 算法为：hash值除以arr数组的长度（这样保证了得到的数组索引是有效的）
* @param key
* @return
*/
private int getIndexOfNode(Object key,LinkedList<Entry> list){
if(list!=null){
for(int i=0;i<list.size();i++){
if(list.get(i).key.equals(key)){
return i;
}
}
}
return -1;
}
private int getIndex(Object key){
return key.hashCode()%arr.length;
}
@Override
public boolean containsKey(Object key) {
int index=getIndex(key);
return getIndexOfNode(key,arr[index])!=-1;
}
@Override
public boolean containsValue(Object value) {
for(int i=0;i<arr.length;i++){
if(arr[i]!=null){
for(int j=0;j<arr[i].size();j++){
if(arr[i].get(j).value.equals(value)){
return true;
}
}
}
}
return false;
}
private class Entry {
Object key;
Object value;
public Object getKey() {
return key;
}
public Object getValue() {
return value;
}
public Entry(Object key, Object value) {
this.key = key;
this.value = value;
}
}
}