说明
是 数组 + 链表 的方式，通过hash算法实现的。是一个典型的用空间换时间的方式。
新版本中有了一些优化，数组+链表实现，当链表中的数据超过8个时，将链表的结果改成了树
import java.util.ArrayList;
public class MyHashMap {
//存放元素的链表数组
private ArrayList[] table;
private int size;
/**
* 构造方法
* 初始化table数组，将初始容量定义为16
*/
public MyHashMap(){
table = new ArrayList[16];
}
/**
* 添加元素
* 当map中已经有对应key的键值对，需要覆盖value的值
* 是覆盖值，没有改变map元素的总数量，不需要size++
* 当map中没有对应key的键值对，需要向集合中添加一组键值对
* 通过hashCode方法可以获取key的hash值，是一个int类型的整数
* 让这个数对16求余，一定得到一个小于16的整数，刚好和table的索引值吻合
* 通过这个数字可以判断key应该存放在table中的那个索引对应的ArrayList
* 如果这个ArrayList为不空，直接创建一个Entry，添加到ArrayList中
* 如果为空，说明这个索引是第一次被访问，需要创建一个ArrayList来存放键值对，然后创建Entry添加到ArrayList中
* size++
* @param key 键
* @param value 值
*/
public void put(Object key, Object value){
Entry entry = getEntry(key);
if(entry != null){
entry.value = value;
}else{
int keyHashCode = key.hashCode();
int index = keyHashCode % 16;
ArrayList list = table[index];
if(list != null){
Entry element = new Entry(key, value, keyHashCode);
list.add(element);
}else{
list = new ArrayList();
table[index] = list;
Entry element = new Entry(key, value, keyHashCode);
list.add(element);
}
size++;
}
}
/**
* 通过key，获取对应的Entry对象
* @param key 键
* @return Entry对象
*/
private Entry getEntry(Object key){
int keyHashCode = key.hashCode();
int index = keyHashCode % 16;
ArrayList list = table[index];
if(list == null || list.size() == 0){
return null;
}else{
for(Object obj : list){
Entry e = (Entry)obj;
if(e.key.equals(key)){
return e;
}
}
return null;
}
}
/**
* 通过键获取值
* @param key 键
* @return 值
*/
public Object get(Object key){
Entry result = getEntry(key);
if(result != null){
return result.value;
}
return null;
}
/**
* 返回map中所有元素的数量
* @return 数量
*/
public int size(){
return size;
}
/**
* 表示键值对的内部类
* @author szsw
*
*/
class Entry{
//键
Object key;
//值
Object value;
//哈希值
int hash;
public Entry(Object key, Object value, int hash) {
this.key = key;
this.value = value;
this.hash = hash;
}
}
}