上海网站开发售后服务,大数据网页制作教程,网络营销的功能有哪些?,php网站如何做多语言当需要判断一个元素是否在集合中时#xff0c;就使用哈希法 散列表#xff08;Hash table#xff0c;也叫哈希表#xff09;#xff0c;是根据键#xff08;Key#xff09;而直接访问在内存存储位置的数据结构。
哈希表中关键码就是数组的索引下标#xff0c;然后通过…当需要判断一个元素是否在集合中时就使用哈希法 散列表Hash table也叫哈希表是根据键Key而直接访问在内存存储位置的数据结构。
哈希表中关键码就是数组的索引下标然后通过下标直接访问数组中的元素复杂度O(1) 哈希表本质上是个数组实现哈希表我们可以采用两种方法
1、数组链表
2、数组二叉树
哈希函数
类似一个函数似的给你一个值经过某些加工得到另外一个值就像这里的给你个人名经过些许加工我们拿到首字母那么这个函数或者是这个方法在哈希表中就叫做散列函数其中规定的一些操作就叫做函数法则
键值对在jdk中就叫Entry
拉链法
刚刚小李和小王在索引1的位置发生了冲突发生冲突的元素都被存储在链表中。 这样我们就可以通过索引找到小李和小王了
其实拉链法就是要选择适当的哈希表的大小这样既不会因为数组空值而浪费大量内存也不会因为链表太长而在查找上浪费太多时间。
线性探测法
使用线性探测法一定要保证tableSize大于dataSize。 我们需要依靠哈希表中的空位来解决碰撞问题。
例如冲突的位置放了小李那么就向下找一个空位放置小王的信息。
set
集合底层实现是否有序数值是否可以重复能否更改数值查询效率增删效率std::set红黑树有序否否O(log n)O(log n)std::multiset红黑树有序是否O(logn)O(logn)std::unordered_set哈希表无序否否O(1)O(1)
std::unordered_set底层实现为哈希表std::set 和std::multiset 的底层实现是红黑树红黑树是一种平衡二叉搜索树所以key值是有序的但key不可以修改改动key值会导致整棵树的错乱所以只能删除和增加。 set会自动将元素排序默认升序排列。 setint s;s.insert(1);s.insert(0);s.insert(3);s.insert(3);s.insert(4);s.insert(7);for (int c : s) {cout c ;}for (setint::iterator it s.begin(); it ! s.end();it) {cout *it endl;}for (setint::iterator it --s.end(); it ! --s.begin(); it--) {cout *it ;}//反向迭代器for (setint::reverse_iterator it s.rbegin(); it ! s.rend();it) {cout *it endl;}
map
映射底层实现是否有序数值是否可以重复能否更改数值查询效率增删效率std::map红黑树key有序key不可重复key不可修改O(logn)O(logn)std::multimap红黑树key有序key可重复key不可修改O(log n)O(log n)std::unordered_map哈希表key无序key不可重复key不可修改O(1)O(1)
std::unordered_map 底层实现为哈希表std::map 和std::multimap 的底层实现是红黑树。同理std::map 和std::multimap 的key也是有序的 红黑树(Red Black Tree)也叫RB树 1为何map和set的插入删除效率比用其他序列容器高
大部分人说很简单因为对于关联容器来说不需要做内存拷贝和内存移动。说对了确实如此。set容器内所有元素都是以节点的方式来存储其节点结构和链表差不多指向父节点和子节点。结构图可能如下 A / \ B C / \ / \ D E F G
因此插入的时候只需要稍做变换把节点的指针指向新的节点就可以了。删除的时候类似稍做变换后把指向删除节点的指针指向其他节点也OK了。这里的一切操作就是指针换来换去和内存移动没有关系。
2为何每次insert之后以前保存的iterator不会失效
iterator这里就相当于指向节点的指针内存没有变指向内存的指针怎么会失效呢(当然被删除的那个元素本身已经失效了)。相对于vector来说每一次删除和插入指针都有可能失效调用push_back在尾部插入也是如此。因为为了保证内部数据的连续存放iterator指向的那块内存在删除和插入过程中可能已经被其他内存覆盖或者内存已经被释放了。即使时push_back的时候容器内部空间可能不够需要一块新的更大的内存只有把以前的内存释放申请新的更大的内存复制已有的数据元素到新的内存最后把需要插入的元素放到最后那么以前的内存指针自然就不可用了。特别时在和find等算法在一起使用的时候牢记这个原则不要使用过期的iterator。
3当数据元素增多时set的插入和搜索速度变化如何
如果你知道log2的关系你应该就彻底了解这个答案。在set中查找是使用二分查找也就是说如果有16个元素最多需要比较4次就能找到结果有32个元素最多比较5次。那么有10000个呢最多比较的次数为log10000最多为14次如果是20000个元素呢最多不过15次。看见了吧当数据量增大一倍的时候搜索次数只不过多了1次多了1/14的搜索时间而已。你明白这个道理后就可以安心往里面放入元素了。
