HashMap
哈希表是一个以数组和单向链表的集合体

数据查询效率高

链表增删效率高

哈希表结合在一起，发挥他们的优点
     哈希表底层源代码
       public class HashMap{
           HashMap底层实际是一个数组
           Node<K,V>[] table
     
           静态内部类HashMap.Node
           static calsss Node<K,V>{
               final int hash; //哈希值(哈希值是 key的hashCode方法的指向结果，hash值通过哈希函数/算法可以转换成储存数组的下标
               final K key; //储存到Map集合中的那个key
               V value; //存储到Map集合中的value
               Node<K,V> next ; //下一个节点的内存地址
           }
       }

就是说，一个节点有四个元素:哈希值,K,V,下一个节点的内存地址

哈希表/散列表：一维数组，这个数组中每一个元素都是一个单向链表(数组和链表的结合体)
put()原理
每次向里面添加K，V的时候会利用Key的hashCode()方法生成一个哈希值（独一无二，类似内存地址）

并用算法决定数组下标，如果下标重复，会拿着Key与此链表里的节点进行equals比对,相同则覆盖数据（意为Key不允许重复），反则往末尾里再添加一个Node（链表添加节点）



get(K)方法
用Key得出哈希值，通过哈希算法得出数组下标，

如果查询这个下标什么都没有，则返回null。

如果有链表，则拿着传入的Key与链表每个节点的Key进行equals比对，

如果不相同返回false，如果相同则返回true ,最终拿到对应的value



为什么说哈希表增删查询效率都很高？

因为

增删在链表上完成

查询只要找部分链表

但是

增删效率没有链表快

查询效率没有数组快

由于哈希值的的原因添加数据随机，所以无序

由于根据key取值，所以不可重复(重复覆盖)

哈希表在添加数据的时候先后调用两个方法，hashCode()和equals()

所以两个方法都要重写

HashMap初始化容量是16，默认加载因子是0.75

默认HashMap集合容量达到75%的时候，数组开始扩容

HashMap集合初始化容量最好是2的倍数

这为了散列分布均匀，为了提高HashMap效率所必须的

在jdk8后，如果哈希表中的单向链表节点超过8的时候，单向链表会变成红黑树数据结构，直到红黑树节点小于6

HashMap,key允许为null

Hashtable,key不允许为null(空指针异常)

Hashtable默认初始容量为11,默认加载因子0.75

扩容：原容量*2+1

本篇要介绍的是一种数据结构——哈希表。
首先回顾一下数组以及链表的内容，我们知道数组有一优点就是存储于数组中的元素便于查找，这跟它的连续存储密切相关。但是它的缺点也很明显，如果我们想添加或者删除一个元素可能需要大幅度的移动数组的元素，效率较低。再看看链表，我们知道链表这种数据结构的优点就是方便在其增加或者删除一个元素，但是查找效率又非常低（必须得从头节点遍历查找）。按照人们的惯性思考——是否能将这两种数据结构结合使用，来达到查询与增删效率上的“中和”呢？答案是可以的，所以就诞生了哈希表这种数据结构。
那么如果将两种数据结构结合使用呢？不难想到，将数组的每个存储单元存储一个链表即可。如图：



把这种数据结构想象成那种串着珠子的落地门帘是不是很形象，（具体叫啥我也不知道哈哈）。

注意：添加节点的过程就用散列函数实现随机，均匀分布在数组中的各个存储空间。如果节点大量集中在一两个存储空间上，那样哈希表这种数据结构就没有意义。

接下来给出一个具体的实例应用，通过这个实例来掌握哈希表这种数据结构：

实例内容：利用哈希表对员工进行操作（包括了添加员工，删除员工，查看员工等等操作）
提示：需要三个类实现，一个是员工类Emp,一个是操作链表的类EmpLinkedList,另一个类是用来管理所有链表上员工节点的类HashTab。

思路：每个员工分配一个编号，根据编号利用散列函数求出员工的具体操作位置，也就是在哪一条链表上进行操作（这里的散列函数用简单的取模运算实现），然后一系列等操作（增加，删除…）就在此链表上进行。
补充：对哈希表的操作实际就是对数组以及链表的操作，建议读者在了解了基本思路就可以自己动手编写，再来对比源码。
具体代码操作：
//管理所有链表上员工节点的类
class HasTab02{
    int size;//数组大小
    Emp2LinkedList[] emp2LinkedLists;//数组元素存放链表
    //构造函数，初始化数组大小
    public HasTab02(int size){
        this.size = size;
        emp2LinkedLists = new Emp2LinkedList[size];
        //当我们创建了数组空间时，此时每个数组单元存储的元素都是null,所以要为每个单元创建对象
        for (int i = 0;i < size;i ++){
            emp2LinkedLists[i] = new Emp2LinkedList();
        }
    }
    //添加
    public void add(Emp2 emp2){
        int no = HashFun(emp2.id);//获取添加Emp在数组中的位置
        emp2LinkedLists[no].add(emp2);
    }
    //遍历
    public void list(){
        for (int i = 0;i < size;i ++){
            emp2LinkedLists[i].list(i + 1);
        }
    }
    //查找
    public void find(int id){
        int no = HashFun(id);
        Emp2 emp2 = emp2LinkedLists[no].find(id);
        if (emp2 == null){
            System.out.println("没有在哈希表中找到该雇员");
        }
        System.out.printf("该雇员所在第%d条链表,id=%d,name=%s\n",no + 1,emp2.id,emp2.name);
    }
    //删除
    public void del(int id){
        int no = HashFun(id);
        emp2LinkedLists[no].del(id);
    }
    //散列函数
    public int HashFun(int id){
        return id % size;
    }
}
//雇员链表
class Emp2LinkedList{
    private Emp2 head;

    /**
     * 添加方法
     * @param emp2 传递雇员
     */
    public void add(Emp2 emp2){
        if (head == null){
            head = emp2;
            return;
        }else {
            Emp2 curEmp = head;//定义辅助指针
            while (true){
                if (curEmp.next == null){
                    break;
                }
                curEmp = curEmp.next;//后移
            }
            //循环结束，curEmp指向了链表最后一个元素
            //默认再链表末尾加入雇员
            curEmp.next = emp2;
        }
    }

    /**
     * 查找方法
     * @param id 查找的id
     * @return 雇员信息
     */
    public Emp2 find(int id){
        if (head == null){
            System.out.println("链表为空");
            return null;
        }
        //辅助指针
        Emp2 curEmp = head;
        while (true){
            if (id == curEmp.id){
                break;
            }
            //如果遍历到了最后还没找到直接赋值null
            if (curEmp.next == null){
                curEmp = null;
                break;
            }
            curEmp = curEmp.next;
        }
        return curEmp;
    }

    /**
     * 删除节点方法
     * @param id 删除id
     */
    public void del(int id){
        if (head == null){
            System.out.println("删除失败，链表为空");
            return;
        }
        //辅助指针
        Emp2 curEmp = head;
        //如果要删除的是链表的第一个节点
        if (head.id == id){
            head = curEmp.next;
            return;
        }
        while (true){
            if (curEmp.next == null){
                System.out.println("删除失败，没有该雇员");
                return;
            }
            //找到待删除节点的前一个节点
            if (curEmp.next.id == id){
                break;
            }
            curEmp = curEmp.next;
        }
        //待删除节点的前一个节点指向待删除节点的后一个节点
        curEmp.next = curEmp.next.next;
    }

    /**
     * 遍历链表
     */
    public void list(int no){
        if (head == null){
            System.out.printf("第%d条链表为空\n",no);
            return;
        }
        System.out.printf("第%d条链表的信息为：",no);
        //head不能动，创建辅助指针
        Emp2 curEmp = head;
        while (true){
            System.out.printf("=>id=%d,name=%s\t",curEmp.id,curEmp.name);
            if (curEmp.next == null){
                break;
            }
            curEmp = curEmp.next;
        }
        System.out.println();
    }
}
//雇员类
class Emp2{
    public int id;
    public String name;
    public Emp2 next;

    public Emp2(int id, String name) {
        this.id = id;
        this.name = name;
    }
}

小小总结一下：哈希表就是数组跟链表的结合，将这两者的优缺点进行“中和”，得到的结果就是在效率上查询以及增删操作整体来看得到改善。如果单一来看，查询效率肯定是不如单一数组的，而增删操作效率肯定不如单一的链表。

JAVA中的哈希表 / 散列表数据结构

HashMap集合底层是哈希表/散列表的数据结构
哈希表数据结构：

哈希表是一个数组和单向链表的结合体

哈希表结合了数组和单向链表的优点，查询效率和增删效率都很高
哈希表：一维数组，数组中的每一个元素都是一个单向链表

引入
二叉搜索树的查找效率为O(log2N)到O(N)，二叉平衡树的查找效率为O(log2N)，那么有没有一种算法可以不经过任何比较，一次直接从表中得到要搜索的元素呢？事实上这种算法是存在的，就是哈希表

1、哈希的概念
元素的存储位置与它的关键码有一一映射的关系，在查找元素的时候不需要进行任何比较，可以直接从表中直接检索出元素的值。
1.1 哈希表的优点
（1）查找的效率高

（2）存在预缓存机制，提高查找的速度
哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)
哈希函数设置：hash(key) = key % capacity;  其中 capacity为存储元素底层空间总的大小

举个栗子：



从上面的这个例子来看，当 key的值为19时，所得的哈希值为1，此时在1 的这个位置已经存在了数据，那么这样的问题就成为哈希冲突，下面我来介绍哈希冲突。

2、哈希冲突
不同关键字通过相同哈希数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。
2.1 引起哈希冲突的原因
引起哈希冲突的主要原因是哈希函数设计的不够合理，才会导致出现多次哈希冲突，一般在设计哈希函数时，选取地址数m附近的一个质数p作为除数(一般是p<=m)，就可以尽可能的避免哈希冲突。
设计哈希函数的原则：

哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
哈希函数计算出来的地址能均匀分布在整个空间中
哈希函数应该比较简单

3、 常用的哈希函数


直接定制法

取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B

优点：简单、均匀

缺点：需要事先知道关键字的分布情况

使用场景：适合查找比较小且连续的情况


除留余数法

设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函

数：Hash(key) = key% p (p<=m),将关键码转换成哈希地址


以上两种哈希函数是最常用的，还有一些不常用的哈希函数，例如：平方取中法、数学分析法、折叠法、 随机数法。
哈希函数设计的越精妙，产生冲突的几率越小
4、 解决哈希冲突的方法
解决哈希冲突的方法有两种，分别为：开散列和闭散列。
4.1 闭散列（开放定址法）
当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。
查找空位置的方法：

1.线性探测

从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。


插入元素

通过哈希函数获取待插入元素在哈希表中的位置，如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素



以上面这个例子来看，当key的序列值为19时，会产生哈希冲突，所以要寻找下一个空位置，即为3所对应的位置。


删除元素

在删除的时候会出现一定的问题，所以不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素1，如果直接删除掉，19查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。


// 哈希表每个空间给个标记
// EMPTY此位置空， EXIST此位置已经有元素， DELETE元素已经删除
enum State{EMPTY, EXIST, DELETE};


线性探测的实现
#pragma once
#include<map>
#include<vector>
using namespace std;

namespace tdd
{
	enum State
	{
		EMPTY,
		EXIST,
		DELETE
	};

class dealInt
{
public:
	int operator()(int n)
	{
		return n;
	}
};

class dealString
{
public:
	int operator()(const string & n)
	{
		int sum = 0;
		int seed = 131;

		for (const char & c : n)
		{
			sum = sum * seed + c;
		}

		return sum & 0x7FFFFFFF;
	}
};

template<class K, class V, class SW>
class hashTable
{
	struct elem
	{
		pair<K, V> m_val;
		State m_state;

		elem(const K & key = K(), const V & val = V(), State state = EMPTY) :
			m_val(key, val),
			m_state(state)
		{

		}
	};

	vector<elem> m_table;
	size_t m_size;
public:
	hashTable(size_t capacity = 11):
		m_table(capacity),
		m_size(0)
		{

		}

	size_t capacity()
	{
		return m_table.size();
	}

private:
	int hashFunc(const K & key)
	{
		SW func;
		return func(key) % capacity();
	}

public:
	bool insert(const pair<K, V> & val)
	{
		int n = hashFunc(val.first);

		while (m_table[n].m_state == EXIST)
		{
			if (m_table[n].m_val.first == val.first)
			{
				return false;
			}

			n++;
			if (n == capacity())
			{
				n = 0;
			}
		}
		m_table[n].m_val = val;
		m_table[n].m_state = EXIST;

		m_size++;
		return true;
	}

	int find(const  K & key)
	{
		int n = hashFunc(key);

		while (m_table[n].m_state != EMPTY)
		{
			if (m_table[n].m_state == EXIST && m_table[n].m_val.first == key)
			{
				return n;
			}
			n++;
			if (n == capacity())
			{
				n = 0;
			}
		}
		return -1;
	}
	bool erase(const K & key)
	{
		int ret = find(key);
		if (ret < 0)
		{
			return false;
		}
		else
		{
			m_table[ret].m_state = DELETE;
			m_size--;
		}
	}

	size_t Size()
	{
		return m_size;
	}

	bool Empty()
	{
		return m_size == 0;
	}

	void Swap(hashTable<K, V, SW> & ht)
	{
		m_table.swap(ht.m_table);
		size_t tmp;

		tmp = m_size;
		m_size = ht.m_size;
		ht.m_size = tmp;
	}
};

};


除留余数法一般选择质数作为除数，原因是为了降低哈希冲突的概率。
闭散列增容


线性探测的优点：实现简单

线性探测的缺点：一旦发生冲突，所有的冲突会连在一起，容易产生数据的“堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。
为了缓解这样的数据堆积，下面来看二次探测

2>二次探测

在线性探测中查找空位置是一个一个挨着找，而二次探测中的查找方法是：H (i) = ( H(0)+i^2 )% m,或者： H(i)= (H(0) - i ^2 )% m。其中：i = 1,2,3…， 是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小。通俗的来讲就是先找右边的一个数据，再找左边的一个数据，例如先找1，再找-1，先找3，再找-3……
**注意：**当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5
由上述可知：二次探测的效率要比线性探测的效率高。

4.2 开散列（开链法）
首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
如下图所示：



从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素
开散列增容
桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下，可能会导致一个桶中链表节点非常多，会影响的哈希表的性能，因此在一定条件下需要对哈希表进行增容，那该条件怎么确认呢？开散列最好的情况是：每个哈希桶中刚好挂一个节点，再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数时，可以给哈希表增容
4.3 开散列与闭散列的比较
应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。事实上： 由于开地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a <= 0.7，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间