0%

手写简易HashMap

发表于 分类于

一，关于哈希表(Hash Table)

定义：散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

​ 给定表H，存在函数hash(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表H为哈希(Hash）表，函数hash(key)为哈希(Hash) 函数。

哈希函数考虑因素：计算哈希函数所需时间，关键字的长度，哈希表的大小，关键字的分布情况，记录的查找频率。

常用方法：

直接定址法：直接以关键字k或者k加上某个常数（k+c）作为哈希地址。

数字分析法：提取关键字中取值比较均匀的数字作为哈希地址。

除留余数法：用关键字k除以某个不大于哈希表长度m的数p，将所得余数作为哈希表地址。

分段叠加法：按照哈希表地址位数将关键字分成位数相等的几部分，其中最后一部分可以比较短。然后将这几部分相加，舍弃最高进位后的结果就是该关键字的哈希地址。

平方取中法：如果关键字各个部分分布都不均匀的话，可以先求出它的平方值，然后按照需求取中间的几位作为哈希地址。

伪随机数法：采用一个伪随机数当作哈希函数。

二，关于哈希冲突：不同key值得到相同地址

解决办法：

  • 开放定址法：开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。
  • 链地址法：将哈希表的每个单元作为链表的头结点，所有哈希地址为i的元素构成一个同义词链表。即发生冲突时就把该关键字链在以该单元为头结点的链表的尾部。
  • 再哈希法：当哈希地址发生冲突用其他的函数计算另一个哈希函数地址，直到冲突不再产生为止。
  • 建立公共溢出区：将哈希表分为基本表和溢出表两部分，发生冲突的元素都放入溢出表中。

三，关于HashMap

定义

​ 基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了不同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。另外，HashMap是非线程安全的，也就是说在多线程的环境下，可能会存在问题，而Hashtable是线程安全的。

​ HashMap 的实例有两个参数影响其性能：初始容量 和加载因子。容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。在Java中，加载因子默认值为0.75，默认初始容量为16 。

​ HashMap是线程不安全的，线程安全用ConcurrentHashMap

解决冲突方法

​ 在Java中，保存数据有两种比较简单的数据结构：数组和链表。数组的特点是：寻址容易，插入和删除困难；而链表的特点是：寻址困难，插入和删除容易。上面我们提到过，常用的哈希函数的冲突解决办法中有一种方法叫做链地址法，其实就是将数组和链表组合在一起，发挥了两者的优势，我们可以将其理解为链表的数组。

哈希函数

​ 在Java 8 之前，HashMap和其他基于map的类都是通过链地址法解决冲突，它们使用单向链表来存储相同索引值的元素。在最坏的情况下，这种方式会将HashMap的get方法的性能从O(1)降低到O(n)。为了解决在频繁冲突时hashmap性能降低的问题，Java 8中使用平衡树来替代链表存储冲突的元素。这意味着我们可以将最坏情况下的性能从O(n)提高到O(logn)。

​ 如果恶意程序知道我们用的是Hash算法，则在纯链表情况下，它能够发送大量请求导致哈希碰撞，然后不停访问这些key导致HashMap忙于进行线性查找，最终陷入瘫痪，即形成了拒绝服务攻击（DDoS）。

1
static int hash(int h) {				//JDK1.7
2
    h ^= (h >>> 20) ^ (h >>> 12);
3
    return h ^ (h >>> 7) ^ (h >>> 4);
4
}
5
static final int hash(Object key) {		//JDK1.8
6
    int hash = (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
7
	int index = hash & (tab.length-1);
8
    return index;
9
}

​ 在JDK1.8的实现中，优化了高位运算的算法，通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的。以上方法得到的int的hash值，然后再通过h & (table.length -1)来得到该对象在数据中保存的位置。

​ 当链表长度大于等于8的时候将链表转换为红黑树，利用红黑树的特点(查找、插入、删除的时间复杂度最坏为O(logn))，可以提高HashMap的性能。当节点个数少于6个的时候，又会将红黑树转化为链表。

四，开始

实现功能：

​ –添加数据，获取键对应值

构建节点

1
class NodeC<K,V> {
2
    final int hash;		//hash值（存储位置）
3
    final K key;		//键
4
    V value;			//值
5
    NodeC<K, V> next;	//下一节点
6
    NodeC(int hash, K key, V value, NodeC<K, V> next) {
7
        this.hash = hash;
8
        this.key = key;
9
        this.value = value;
10
        this.next = next;
11
    }
12
}

构造HashMap

1
public class HashMapC<K,V>{
2
    int size;						//长度
3
    NodeC<K,V> table[];				//数组
4
5
    public HashMapC() {
6
        table=new NodeC[16];		//默认长度16（2的整数次幂）
7
    }

哈希函数

1
final int hash(Object key) {		//JDK8同款
2
    int h;
3
    int hash = (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
4
    int index = hash & (table.length-1);
5
    //System.out.println("hash值为："+index);
6
    return index;
7
}

添加数据[put(K k,V v)]

1
public void put(K k,V v){
2
        int h=hash(k);						//计算哈希值
3
        NodeC nc=new NodeC(h,k,v,null);		//新建节点
4
        NodeC temp=table[h];				//找到该节点对应位置的链表
5
        Boolean flag=false;
6
        if(temp==null){
7
            table[h]=nc;					//该链表暂时没有数据，将节点放入
8
            size++;
9
        }else {
10
            while (temp!=null){				//遍历链表
11
                if(temp.key==k){			//发现同一个键，覆盖value值
12
                    temp.value=v;
13
                    flag=true;
14
                    break;
15
                }
16
                if(temp.next==null){		//没有下一个节点，结束遍历
17
                	break;
18
            	}
19
                temp=temp.next;
20
            }
21
            if(!flag){
22
                temp.next=nc;				//为新元素，加载表尾
23
                size++;
24
            }
25
        }
26
    }

获取key值对应的value值[get(K k)]

1
public V get(K key){
2
    int h=hash(key);						//计算哈希值
3
    NodeC<K,V> temp=table[h];				//找到链表
4
    while (temp!=null){
5
        if (temp.key==key) {				//找到键，返回值
6
            return temp.value;				
7
        }
8
        temp=temp.next;
9
    }
10
    return null;							//没找到，返回null
11
}

重写toString方法便于观察

1
@Override
2
public String toString(){
3
    StringBuilder result=new StringBuilder("{");
4
    for(int i=0;i<table.length;i++){			//从第一个链表开始遍历
5
        if(table[i]==null){						//跳过空节点
6
            continue;
7
        }else {
8
            while (table[i]!=null) {			//遍历链表所有节点
9
                result.append(table[i].key+" = "+table[i].value+"，");
10
                table[i]=table[i].next;
11
            }
12
        }
13
    }
14
    if(!result.equals("{")){
15
        result.setCharAt(result.length()-1,'}');//删除最后的逗号
16
    }else {
17
        result.append("}");
18
    }
19
    return result.toString();
20
}

五，测试方法

1
public static void main(String[] args) {
2
    HashMapC<Integer,String> hmc=new HashMapC<>();
3
    hmc.put(1,"一");
4
    hmc.put(2,"二");
5
    hmc.put(3,"三");
6
    hmc.put(4,null);
7
    hmc.put(17,"十七");
8
    hmc.put(18,"十八");
9
    hmc.put(33,"三十三");
10
    hmc.put(1,"111");
11
    System.out.println(hmc.get(1));
12
    System.out.println(hmc.get(3));
13
    System.out.println(hmc.get(18));
14
    System.out.println(hmc.get(33));
15
    System.out.println("end...");
16
    System.out.println(hmc);
17
    System.out.println(hmc.size);
18
    HashMapC<String,Integer> hmc2=new HashMapC<>();
19
    hmc2.put("a",1);
20
    hmc2.put("b",2);
21
    hmc2.put("k",3);
22
    hmc2.put("z",4);
23
    System.out.println(hmc2.get("a"));
24
    System.out.println(hmc2.get("b"));
25
    System.out.println(hmc2.get("k"));
26
    System.out.println(hmc2.get("z"));
27
    System.out.println(hmc2);
28
}

六，总结

头发-1