Map
最经典的数据结构：数组 + 链表
自定义Map接口
面向接口的编程思想。
public interface KJMap<K,V> {
//KJMap基本功能 快速存、取
//存
public V put(K k,V v);
//取
public V get(K k);
//定义一个内部接口，用存储k、v，并提供获得k、v的方法
public interface Entry<K,V>{
//map.getKey
public K getKey();
public V getValue();
}
}
自定义Map实现类
成员变量
//定义默认数组大小 16
public static int defaultLenth = 1 << 4; //2 2 2 2 位运算
//扩容标准 useSize/defaultLenth
private static double defaulAddSizeFactor = 0.75;
//使用数组位置的总数
private int useSize;
//定义Map 骨架
public Entry<K,V>[] table = null;
Entry<K,V>实现类
class Entry<K, V> implements KJMap.Entry<K, V>{
K k;
V v;
//指向被this压下去的Entry对象
Entry<K, V> next;
public Entry(K k, V v, Entry<K, V> next) {
this.k = k;
this.v = v;
this.next = next;
}
@Override
public K getKey() {
return k;
}
@Override
public V getValue() {
return v;
}
}
构造函数
//SPRING 门面模式
public KJHashMap() {
this(defaultLenth,defaulAddSizeFactor);
}
//初始化容器
public KJHashMap(int length, double defaulAddSizeFactor) {
//参数判断
if(length < 0){
throw new IllegalArgumentException("参数不能为负数" + length);
}
if(defaulAddSizeFactor <= 0 || Double.isNaN(defaulAddSizeFactor)){
throw new IllegalArgumentException("扩容标准必须是大于0的数字" + defaulAddSizeFactor);
}
//赋值
this.defaultLenth = length;
this.defaulAddSizeFactor = defaulAddSizeFactor;
table = new Entry[defaultLenth];
}
存
@Override
public V put(K k, V v) {
//判断是否需要扩容
if(useSize > defaulAddSizeFactor * defaultLenth){
//2倍扩容
up2Size();
}
//获得添加的数组位置 索引
int index = getIndex(k,table.length);
//赋值
//获得索引值对象
Entry<K,V> entry = table[index];
if(entry == null){
//当前索引位置无元素
table[index] = new Entry<>(k,v,null);
//数组大小 +1
useSize++;
}else if(entry != null){
//当前索引位置有元素 链表结构 next
table[index] = new Entry<>(k,v,entry);
}
return table[index].getValue();
}
扩容（数据大小二倍扩容）
private void up2Size() {
//新建2倍空间的数组
Entry<K, V>[] newtTable = new Entry[2 * defaultLenth];
//将老数组的内容拿到新数组当中
againHash(newtTable);
}
数据拷贝
private void againHash(Entry<K,V>[] newtTable) {
//entry对象列表
List<Entry<K, V>> entryList = new ArrayList<Entry<K, V>>();
// for出来就代表内容全部遍历到entryList当中
for (int i = 0; i < table.length; i++) {
if (table[i] == null) {
continue;
}
// 继续找存到数组上的Entry对象、赋值entryList
foundEntryByNext(table[i], entryList);
}
//再次初始化Map对象
if(entryList.size() > 0){
this.table = newtTable;
this.defaultLenth = 2 * defaultLenth;
useSize = 0;
for (Entry<K, V> entry : entryList) {
if (entry.next != null) {
//独立的关系，从新hash
entry.next = null;
}
put(entry.getKey(), entry.getValue());
}
}
}
查找所有的entry对象
private void foundEntryByNext(Entry<K,V> entry, List<Entry<K,V>> entryList) {
if (entry != null && entry.next != null) {
entryList.add(entry);
// 有链表递归 不断的一层一层取存entry
foundEntryByNext(entry.next, entryList);
} else {
// 没有链表的情况
entryList.add(entry);
}
}
添加查找位置定位
private int getIndex(K k,int length){
int m = length - 1;
//当 lenth = 2n 时，X % length = X & (length - 1) 位运算效率高
int index = hash(k.hashCode()) & m;
return index;
}
hash算法（减少碰撞 - 链表）
//定义自己的hash算法 TODO
private int hash(int hashCode){
hashCode = hashCode ^ ((hashCode >>> 20) ^ (hashCode >>> 12));
return hashCode ^ ((hashCode >>> 7) ^ (hashCode >>> 4));
}
取
@Override
public V get(K k) {
//获得查询的数组位置 索引
int index = getIndex(k,table.length);
if(table[index] == null){
throw new NullPointerException();
}
//key存在链表的情况（next） 通过key值比较
return findValueByEqualKey(k,table[index]);
}
链表对比key值
private V findValueByEqualKey(K k, Entry<K,V> entry) {
if(k == entry.getKey() || k.equals(entry.getKey())){
return entry.getValue();
} else if(entry.next != null){
//递归查询 和k相同的entry
return findValueByEqualKey(k,entry.next);
}
return null;
}
数组大小
public int getUseSize() {
return useSize;
}
