unordered系列关联式容器

unordered_map&& unordered_set

关联性容器介绍

在STL底层map和set使用红黑树封装实现的，而其复杂度为基本为logn因为高度可控，但往后发展还是有大神想出了另一种容器结构也就是哈希。也就是底层用哈希来封装出map和set

介绍

1. unordered_map是存储<key, value>键值对的关联式容器，其允许通过keys快速的索引到与其对应的value。
2. 在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。
3. 在内部,unordered_map没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。
4. unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。
5. unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问value。
6. 它的迭代器至少是前向迭代器。
   注意：unordered_map中key是不能重复的，因此count函数的返回值最大为1
   无论是unordered_map/se其使用规则和map和set没有多大差别就是底层实现不同。效率不同。

底层结构

哈希概念

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(N)，搜索的效率取决于搜索过程中元素的比较次数。

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

插入元素：
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放

搜索元素：
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)

例如：
每次给一个数对其进行取模，得到一个值对其进行插入，有点之前计数排序那意思。

差的元素多了不可避免地就会有重复的字眼。

哈希冲突

对于不同关键字取模相同出一样的哈希地址，这个我们叫做哈希冲突。
通过哈希函数来解决。
设计原则：

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

常见哈希函数：直接定制法，除留余数法，平方取中法，折叠法，随机数法，数学分析法。
经常用的就是前两个

注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突

闭散列

闭散列介绍

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个”空位置中去

1.线性探测
对于已经冲突的关键字，我们对其进行线性查找，通过哈希函数找到对应的位置，若没有就插入，若有就一次往后找空位置插入。

这里就对于散列的每一个位置进行状态的定义，采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素

扩容机制：
当所有元素插满时候，其状态都为存在那么就无法找出对应空的位置一致循环下去，所以我们要保证闭散列不能为满或者不能使它快满了，在达到一定的比例时，就要对其进行扩容机制。

2.二次探测
可以通过一次探测得出如果同一块区域有大量的数据堆积在一起，效率会降低，也就是将一个个探测变成次方的查找

研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。
空间利用率比较低，哈希的缺陷

实现

	enum State
	{
		EXIST,
		EMPTY,
		DELETE,
	};

	template<class T>
	struct HashNode
	{
		State _state = EMPTY; // 状态
		T _t;
	};

	template<class K, class T, class HashFunc = Hash<K>>
	class HashTable
	{
	public:
		bool Insert(const T& t)
		{
			// 负载因子>0.7就增容
			if (_tables.size() == 0 || _size * 10 / _tables.size() == 7)
			{

				size_t newsize = GetNextPrime(_tables.size());


				HashTable<K, T> newht;
				newht._tables.resize(newsize);
				for (auto& e : _tables)
				{
					if (e._state == EXIST)
					{
						// 复用冲突时探测的逻辑
						newht.Insert(e._t);
					}
				}

				_tables.swap(newht._tables);
			}

			HashNode<T>* ret = Find(t);
			if (ret)
				return false;


			size_t start = t % _tables.size();
			// 线性探测，找一个空位置
			size_t index = start;
			size_t i = 1;
			while (_tables[index]._state == EXIST)
			{
				index = start + i;
				index %= _tables.size();

				++i;
			}

			_tables[index]._t = t;
			_tables[index]._state = EXIST;
			_size++;

			return true;
		}

如果传入的是个字符串，那么我们就需要将其转成ASC||码进行计算，就需要引入仿函数特化一个结构体如果传入的是string就去调特化的。

template<class K>
struct Hash
{
	size_t operator()(const K& key)
	{
		return key;
	}
};

// 特化
template<>
struct Hash < string >
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto ch : s)
		{
			//hash += ch;
			hash = hash * 131 + ch;
		}

		return hash;
	}
};

当然查找和删除也类似：查找存在并且相等的值，遇到空则失败。删除就得先查找然后设置状态。插入的时候要先对其进行查找如果有了就失败

开散列

介绍

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

开散列增容机制

开散列的扩容机制不会让自己的插入影响，如果通过一个桶中插入的节点过多不回去影响其他的只会影响自己的效率，最好的情况就是每个桶中一个节点就是不需要二次搜索，不会出现哈希冲突。

实现

当进入size为0就给第一个素数（这里大神们研究的通过开成某些素数大小的容量不容易冲突），创建一个新对象并将旧表上的点一个个的插入新表当中，然后释放旧表节点并至空。

pair<Node*, bool> Insert(const T& t)
		{
			KeyOfT kot;
			// 负载因子 == 1时增容
			if (_size == _tables.size())
			{
				size_t newsize = GetNextPrime(_tables.size());
				vector<Node*> newtables;
				newtables.resize(newsize, nullptr);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					// 旧表中节点直接取下来挂到新表
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;
						size_t index = HashFunc(kot(cur->_t), newtables.size());
						// 头插
						cur->_next = newtables[index];
						newtables[index] = cur;
						cur = next;
					}
					_tables[i] = nullptr;
				}
				newtables.swap(_tables);
			}
			size_t index = HashFunc(kot(t), _tables.size());
			// 查找t在在不在
			Node* cur = _tables[index];
			while (cur)
			{
				if (kot(cur->_t) == kot(t))
					return make_pair(cur, false);
				cur = cur->_next;
			}
			Node* newnode = new Node(t);
			newnode->_next = _tables[index];
			_tables[index] = newnode;
			return make_pair(newnode, true);
		}

开散列和闭散列比较

应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。事实上： 由于开地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a <= 0.7，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间

一、冲突——概念

不同关键字通过相同的哈希函数计算出相同的哈希地址，该种现象称为哈希冲突或者哈希碰撞。
首先，我们要明确一点，由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的，这就导致一个问题，冲突的发生是必然的，我们能做的是尽量降低冲突率。

二、冲突——避免——哈希函数设计

引起哈希冲突的一个原因可能是：哈希函数设计不够合理。

1.哈希函数设计原则

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

2.常见哈希函数

1.直接定制法
取关键字的某个线性函数为散列地址：Hash(Key)=A*Key+B
优点：简单、均匀
缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且连续的情况

2.除留余数法
设置列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key)=key%p(p<=m),将关键码转换成哈希地址。
还有平方取中法、折叠法、随机数法和数学分析法等几种不常用的方法，这里不再作过多阐述。
注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突。

二、冲突——解决——闭散列

1.概念

当发生哈希冲突时，从发生哈希冲突的位置开始按照某种方式找“下一个”空位置。
1.通过哈希函数计算哈希地址
2.插入元素----注意：可能会产生哈希冲突

找“下一个”空位置的方式：

1.线性探测

从发生哈希冲突的位置开始，逐个挨着依次往后查找，如果走到空间末尾再从头开始。
那么我们这里要插入36，求出哈希地址为6，但此位置已经被占据，我们就挨着往后进行查找，走到8号位置发现是空的，插入36即可。
那么这里有一个问题：我们怎么知道哪个位置有元素，哪个位置没有元素呢？
所以这里我们要给哈希表格中的每个空间进行状态标记：
有元素：EXIST 无元素：EMPTY

查找要插入的位置：

但是当删除表格内元素的时候，就会出现一些意外的情况：
当我们要删除6时，先要计算6的哈希地址，算出来为6号位置，直接将该位置状态修改成EM，但是如果把该位置修改了，就会造成我们后边的36找不到，因为我们要删除36求其哈希地址为6，但是6号位置已经为空了，就不会再往后找了，这样就会导致后期有些元素找不到。
所以在删除元素时，不能直接将其状态改为EM，得需要再给一个状态DELETE，表明该位置上的元素被删除了，所以把6删完，将其状态改为DELETE，说明该位置之前有元素，只是后来被删除了而已，我们就可以往后查找，就可以找到36。

但是我们会发现，上面写的程序最终会进入死循环，其实前面这种事有很大问题的，当表格快要存满时，哈希表的效率就会降低，发生冲突的概率也会升高
比如下图：当我们要在此基础上插入44时，我们需要从四号位置一直走，知道走到3号位置，效率很低了

因此哈希表格当中是不会将元素存满的，那么存多少个才算合适呢？
存的少了空间利用率不高，存的多了冲突的概率就大。

负载因子调节：
散列表中负载因子的定义为：α=填入表中的元素个数 / 散列表的长度
负载因子越小：存的元素越少，发生冲突的概率越低

负载因子的冲突率的关系粗略演示：

负载因子应严格限制在0.7~0.8以下，在线性探测中，我们一般情况下规定负载因子为0.75。
已知哈希表中已有的关键字个数是不可变的，那我们能调整的就只有哈希表中数组的大小。

优点：
处理哈希冲突的方式简单—逐个挨着依次往后找

缺陷：
容易产生数据的堆积—一旦发生冲突，数据就容易连成一片。

解决方式： 二次探测

2.二次探测

线性探测的缺陷就是产生冲突的数据堆积在一块，这与其找下一个空位置有关，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：Hi=(H0+i²)%m，或者：Hi=(H0-i²)%m。 其中：i=1，2，3…，H0是通过散列函数Hash(x)计算出来的哈希地址，m是表的大小。
如果index越界，接着取模运算

优点：
解决了线性探测数据堆积的问题。

缺陷：
当表格中的元素不断增多，二次探测可能要找的次数更多

所以二次探测的负载因子可能会被放得很低，比如α=0.5。

三、冲突——解决——开散列

1.概念

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

2.开散列的模拟实现

    public static class ListNode{
        private int key;
        private int value;
        ListNode next;

        public ListNode(int key,int value){
            this.key=key;
            this.value=value;
        }
    }

2.创造一个数组用来存放链表的头结点并定义初始容量

    ListNode[] table;
    int size;

    public HashBucket(int initCapacity){
        initCapacity=initCapacity<=0?16:initCapacity;
        table=new ListNode[initCapacity];
    }

    private int size(){
        return size;
    }

3.写哈希函数

    private int hashFunc(int key){
        return key%table.length;
    }

4.V put(K key,V value) ：插入元素 O(1)

根据哈希函数找到对应的桶号
遍历该链表，如果找到相等的就替换value并返回旧的value
没有相等的则将新的头插在链表中

    public int put(int key,int value){
        //求初始哈希地址
        int hash=hashFunc(key);
        //找到对应的链表
        ListNode cur=table[hash];
        while(cur!=null){
            //相等则替换
            if(key==cur.key){
                int oldValue=cur.value;
                cur.value=value;
                return oldValue;
            }
            cur=cur.next;
        }
        //不相等则头插
        ListNode newNode=new ListNode(key,value);
        newNode.next=table[hash];
        table[hash]=newNode;
        size++;
        return value;
    }

5.V get(Object key) ：获取key对应的value O(1)

根据哈希函数找到对应的桶号
遍历该桶号所对应的链表，如果key相等返回对应的value，如果没有找到则返回null

    public Integer get(int key){
        int hash=hashFunc(key);

        ListNode cur=table[hash];
        while(cur!=null){
            if(cur.key==key){
                return cur.value;
            }
            cur=cur.next;
        }
        return null;
    }

6.V getOrDefault(Object key,V defaultValue)：获取key对应的value，如果没有返回设置的默认值

根据get方法来写
如果找到则返回get方法的结果
未找到则返回默认值

    public int getOrDefault(int key,int defaultValue){
        Integer ret=get(key);
        return ret!=null?ret:defaultValue;
    }

7.V remove(Object key)：移除对应元素

根据哈希函数计算key所在的桶号找到对应链表
如果链表的第一个就是要删除的，直接将下一个的地址放入对应桶中
如果是后面的，设置一个prev来标记前一个结点，prev.next=cur.next
cur.next==null

    public int remove(int key){
        int hash=hashFunc(key);

        ListNode cur=table[hash];
        int oldValue=0;
        //第一个就是要删除的
        if(key==cur.key){
            oldValue=cur.value;
            //直接将下一个的地址放在哈希桶中
            table[hash]=cur.next;
            cur.next==null;
        }
        //普遍情况
        //设置prev来标记前一个
        ListNode prev=cur;
        cur=cur.next;
        while(cur!=null){
            if(cur.key==key){
                oldValue=cur.value;
                prev.next=cur.next;
                cur.next=null;
            }
            prev=cur;
            cur=cur.next;
        }
        size--;
        return oldValue;
    }

8.boolean containsKey(Object key)：判断是否包含key对应元素 O(1)

得到key所对应的桶号
利用之前写过的get(key)方法
为空说明没找到返回false
不为空找到，返回true

    public boolean containsKey(int key){
        int hash=hashFunc(key);
        return get(key)==null?false:true;
    }

9.boolean containsValue(Object value) ：判断是否包含value对应元素 O(N)

因为桶中所有元素是根据key联系起来的，与value无关
所以这里查找value只能采用全部遍历的方法

    public boolean containsValue(int value){
        //遍历桶中所有元素
        for(int i=0;i<table.length;i++){
            ListNode cur=table[i];
            while(cur!=null){
                if(cur.value==value){
                    return true;
                }
                cur=cur.next;
            }
        }
        //遍历所有后没找到
        return false;
    }

10.主方法：

    public static void main(String[] args) {
        HashBucket hb=new HashBucket(10);

        int[] array={1,7,6,4,5,9};
        for(int i=0;i<array.length;i++){
            hb.put(array[i],array[i]);
        }

        System.out.println(hb.size());
        hb.put(7,8);
        System.out.println(hb.size());

        System.out.println(hb.get(7));

        System.out.println(hb.getOrDefault(7,7));

        System.out.println(hb.getOrDefault(10,10));

        System.out.println(hb.containsKey(7));

        System.out.println(hb.containsValue(7));

        hb.remove(7);
        System.out.println(hb.containsKey(7));
    }
}

输出结果：

由于我们在查找key时，最多也就是遍历完一个链表，其中中每个链表又不会很长，所以时间复杂度为O(1)
而在查找value时需要对所有元素都遍历一遍，时间复杂度为O(N)

哈希桶什么情况下达到最优？

空间利用率尽可能高：每个桶都将其利用上
这种状态一旦出现，再继续插入元素，必然会发生冲突

因此我们可以设置当哈希桶中的元素个数和桶的个数相同时，进行扩容，例如下图：

一般扩容都是按照两倍的方式来的

代码实现：

    private void checkCapacity(){
        if(size>= table.length){
            int newCapacity=table.length*2;
            ListNode[] newTable=new ListNode[newCapacity];

            //逐个桶进行搬移---逐条链表进行搬移
            for(int i=0;i<table.length;i++){
                ListNode cur=table[i];
                while(cur!=null){
                    //将cur先从table[i]桶中移除---类似头删
                    table[i]=cur.next;
                    //将cur往newTable中插入
                    int bucketNo=cur.key%newTable.length;
                    newTable[bucketNo]=cur;
                    cur=table[i];
                }
            }
            table=newTable;
        }
    }

同时在put方法中添加第0步：检查是否需要扩容。

解决哈希冲突两种常见的方法是：闭散列和开散列

闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去

1. 线性探测
比如场景，现在需要插入元素44，先通过哈希函数计算哈希地址，下标为4，因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突。
线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
插入通过哈希函数获取待插入元素在哈希表中的位置如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素.

采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。

2. 二次探测
线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：H_i = (H_0 + i^2 )% m,
或者：H_i = (H_0 - i^2 )% m。其中：i = 1,2,3…， H_0是通过散列函数Hash(x)对元素的关键码 key进行计算得到的位置，m是表的大小。 对于2.1中如果要插入44，产生冲突，使用解决后的情况为：

研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。
因此：闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。

开散列/哈希桶

**开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，**具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

通过顺序表和链表实现（顺序表中存储的哈希函数的地址，除留余数法，顺序表的每个位置就是一个桶），开散列中每个桶中放的都是发生哈希冲突的元素。

冲突严重时的解决办法

1. 每个桶的背后是另一个哈希表
2. 每个桶的背后是一棵搜索树

代码实现哈希桶

// key-value 模型
public class HashBucket {
    private static class Node {
        private int key;
        private int value;
        Node next;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private Node[] array;
    private int size; // 当前的数据个数
    private static final double LOAD_FACTOR = 0.75;

    public int put(int key, int value) {
        int index = key % array.length;
// 在链表中查找 key 所在的结点
// 如果找到了，更新
// 所有结点都不是 key，插入一个新的结点
        for (Node cur = array[index]; cur != null; cur = cur.next) {
            if (key == cur.key) {
                int oldValue = cur.value;
                cur.value = value;
                return oldValue;
            }
        }
        Node node = new Node(key, value);
        node.next = array[index];
        array[index] = node;
        size++;
        if (loadFactor() >= LOAD_FACTOR) {
            resize();
        }
        return -1;
    }

    private void resize() {
        Node[] newArray = new Node[array.length * 2];
        for (int i = 0; i < array.length; i++) {
            Node next;
            for (Node cur = array[i]; cur != null; cur = next) {
                next = cur.next;
                int index = cur.key % newArray.length;
                cur.next = newArray[index];
                newArray[index] = cur;
            }
        }
        array = newArray;
    }

    private double loadFactor() {
        return size * 1.0 / array.length;
    }

    public HashBucket() {
        array = new Node[8];
        size = 0;
    }

    public int get(int key) {
        int index = key % array.length;
        Node head = array[index];
        for (Node cur = head; cur != null; cur = cur.next) {
            if (key == cur.key) {
                return cur.value;
            }
        }
        return -1;
    }
}

性能分析

虽然哈希表一直在和冲突做斗争，但在实际使用过程中，我们认为哈希表的冲突率是不高的，冲突个数是可控的，也就是每个桶中的链表的长度是一个常数，所以我们认为哈希表的插入/删除/查找时间复杂度是O(1) 。