开发大型网站的流程图,成都公司注册价格,湖南做网站kaodezhu,wordpress memcache目录
一、搜索模型
二、Map
2.1 Map.Entry
2.2 Map 方法
2.3 Map 注意事项
三、Set
3.1 Set 方法
3.2 Set 注意事项
四、哈希表
4.1 哈希表
4.2 冲突
4.3 哈希函数设计
4.4 闭散列
4.5 开散列/哈希桶
总结 【搜索树】 二叉搜索树又称二叉排序树#xff0c;它或…目录
一、搜索模型
二、Map
2.1 Map.Entry
2.2 Map 方法
2.3 Map 注意事项
三、Set
3.1 Set 方法
3.2 Set 注意事项
四、哈希表
4.1 哈希表
4.2 冲突
4.3 哈希函数设计
4.4 闭散列
4.5 开散列/哈希桶
总结 【搜索树】 二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树 1、若它的左子树不为空则左子树上所有节点的值都小于根节点的值。 2、若它的右子树不为空则右子树上所有节点的值都大于根节点的值。 3、它的左右子树也分别为二叉搜索树。 一、搜索模型
搜索的数据称为关键字 (Key)关键字对应的称为值 (Value)将其称之为键值对 (Key-Value)。
1、纯 Key 模型
例如有一个英文词典查找一个单词是否在词典中。
2、Key-Value 模型
例如有一个文件统计文件中每个单词出现的次数统计结果是每个单词都有与其对应的次数单词单词出现的次数。 Map 和 Set 是一种专门用来进行动态搜索的数据结构其搜索的效率与其具体的实例化子类有关。Map 中存储的就是 Key-Value而 Set 中只存储了 Key。 二、Map
Map 是一个接口类该类没有继承自 Collection该类中存储的是 K,V 结构的键值对并且 K 一定是唯一的不能重复。
2.1 Map.Entry
Map.EntryK,V 是 Map 内部实现的用来存放 key,value 键值对映射关系的内部类可以理解为一个存放键值对的容器。
方法说明K getKey()返回 entry 中的 keyV getValue()返回 entry 中的 valueV setValue(V value)将键值对中的 value 替换为指定的 value
注Map.EntryK,V 中并并没有提供设置 Key 的方法。 2.2 Map 方法
方法说明V get(Object key)返回 key 对应的 valueV getOrDefault(Object key, V defaultValue)返回 key 对应的 valuekey 不存在返回默认值V put(K key, V value)设置 key 对应的 valueV remove(Object key)删除 key 对应的映射关系SetK keySet()返回所有 key 的不重复集合CollectionV values()返回所有 value 的可重复集合SetMap.EntryK, V entrySet()返回所有的 key-value 映射关系boolean containsKey(Object key)判断是否包含 keyboolean containsValue(Object value)判断是否包含 value 2.3 Map 注意事项 1、Map 是一个接口不能直接实例化对象如果要实例化对象只能实例化其实现类TreeMap 或者 HashMap。 2、Map 中存放键值对的 key 是唯一的value 是可以重复的。 3、在 TreeMap 中插入键值对时key 不能为空否则就会抛 NullPointerException 异常value 可以为空。但是 HashMap 的 key 和 value 都可以为空。 4、Map 中的 key 可以全部分离出来存储到 Set 中来进行访问 (因为Key不能重复)。 5、Map 中的 value 可以全部分离出来存储在 Collection 的任何一个子集合中 (value可能有重复)。 6、Map 中键值对的 key 不能直接修改value 可以修改如果要修改 key需先删除再重新插入。 【TreeMap 和 HashMap 的区别】
Map底层结构 TreeMapHashMap底层结构红黑树哈希桶插入/删除/查找时间复杂度O(1)是否有序关于Key有序无序线程安全不安全不安全插入/删除/查找区别需要进行元素比较通过哈希函数计算哈希地址比较与覆写key 必须能够比较否则会抛出 ClassCastException 异常自定义类型需要覆写 equals 和 hashCode 方法应用场景需要 Key 有序场景下Key 是否有序不关心需要更高的时间性能 三、Set
Set 与 Map 主要的不同有两点
1、Set 是继承自 Collection 的接口。
2、Set 中只存储了 Key。
3.1 Set 方法
方法说明boolean add(E e)添加元素但重复元素不会被添加成功void clear()清空集合boolean contains(Object o)判断 o 是否在集合中IteratorE iterator()返回迭代器boolean remove(Object o)删除集合中的 oint size()返回 set 中元素的个数boolean isEmpty()检测 set 是否为空空返回 true否则返回 falseObject[] toArray()将 set 中的元素转换为数组返回boolean containsAll(Collection? c)集合 c 中的元素是否在 set 中全部存在是返回 true否则返回 falseboolean addAll(Collection? extends E c)将集合 c 中的元素添加到 set 中可以达到去重的效果 3.2 Set 注意事项 1、Set 是继承自 Collection 的一个接口类。 2、Set 中只存储了 key并且要求 key 一定要唯一。 3、TreeSet 的底层是使用 Map 来实现的其使用 key 与 Object 的一个默认对象作为键值对插入到 Map 中的。 4、Set 最大的功能就是对集合中的元素进行去重。 5、实现 Set 接口的常用类有 TreeSet 和 HashSet还有一个 LinkedHashSetLinkedHashSet 是在 HashSet 的基础上维护了一个双向链表来记录元素的插入次序。 6、Set 中的 Key 不能修改如果要修改需删除后重新插入。 7、TreeSet 中不能插入 null 的 keyHashSet 可以。 【TreeSet 和 HashSet 的区别】 Set底层结构 TreeSetHashSet底层结构红黑树哈希桶插入/删除/查找时间复杂度O(1)是否有序关于 Key 有序不一定有序线程安全不安全不安全插入/删除/查找区别按照红黑树的特性通过哈希函数计算哈希地址比较与覆写key 必须能够比较否则会抛出 ClassCastException 异常自定义类型需要覆写 equals 和 hashCode 方法应用场景需要 Key 有序场景下Key 是否有序不关心需要更高的时间性能 四、哈希表
4.1 哈希表
哈希(散列)方法可以通过哈希(散列)函数使元素的存储位置与它的关键码之间建立一一映射的关系构造出哈希表(散列表)。哈希表可以在查找时不经过任何比较一次直接从表中得到要搜索的元素。
例如数据集合 {153769}
哈希函数设计为hash(key) key % capacitycapacity 为存储元素空间总大小。由此计算出该元素的哈希地址即可存储该元素。 可以看出使用哈希方法进行搜索不用进行多次关键码的比较搜索速度很快。可若往数据集合中插入元素 17由于 17 % 10 7故元素 7 与元素 17 会产生冲突。 4.2 冲突
不同关键字通过相同哈希函数计算出相同的哈希地址这种现象称为哈希冲突 (哈希碰撞)。
把具有不同关键码二具有相同哈希地址的数据元素称为同义词。 4.3 哈希函数设计
由于哈希表容量小于实际要存储的关键字数量所有发生冲突是必然的我们能做的只是尽量降低冲突率。
引起哈希冲突的一个原因哈希函数设计不够合理哈希函数设计原则 1、哈希函数的定义域必须包括需要存储的全部关键码而如果哈希表允许有 m 个地址时其值域必须在 0 到 m-1 之间。 2、哈希函数计算出来的地址能均匀分布在整个空间中。 3、哈希函数应该比较简单。 【常见哈希函数】
1、直接定制法
取关键字的某个线性函数为哈希地址hash(Key) A*key B。 优点简单、均匀。 缺点需要事先知道关键字的分布情况。 使用场景适合查找比较小且连续的情况。 2、除留余数法
设哈希表中允许的地址数为 m取一个不大于 m但最接近或者等于 m 的质数 p 作为除数按照哈希函数hash(key) key % p(pm)将关键码转换成哈希地址。 【负载因子调节】
哈希表的载荷因子定义为α 存入表中的元素个数 / 哈希表的长度。
α 是哈希表装满程度的标志因子。由于表长是定值故 α 与 存入表中的元素个数 成正比α 越大存入表中的元素个数 越多产生冲突的可能性就越大。故为了降低冲突率当 α 达到一定程度时我们需要扩容 哈希表的长度。例如Java 的系统库中限制了载荷因子为 0.75超过此值将 resize 哈希表。 解决哈希冲突的两种常见方法是闭散列和开散列。 4.4 闭散列
闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把 key 存放到冲突位置中的下一个空位置中去。故又有了两种方法将冲突的元素存至其他位置。
1、线性探测 从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止。 例如上文中需要再插入元素 17此时通过哈希函数计算出哈希地址为 7但发生了哈希冲突。故用到线性探测寻找到下标 8 为空存入元素 17。 若再插入元素 27即继续线性探测寻找到下标 0 为空存入元素 27。 2、二次探测
线性探测的缺陷是产生冲突的数据堆积在一块因此二次探测为了避免该问题找下一个空位置的方法为其中 i 1,2,3,……是通过哈希函数计算得到的哈希地址m 是表的大小。
故若插入元素 17 发生哈希冲突使用二次探测 闭散列最大的缺陷就是空间利用率比较低这也是哈希的缺陷。 4.5 开散列/哈希桶
开散列法又叫链地址法(开链法)首先对关键码集合用哈希函数计算哈希地址具有相同地址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中。 从上图可以看出开散列中每个桶中放的都是发生哈希冲突的元素。此时插入元素 17 和 27 会得到 开散列可以理解为把一个在大集合中的搜索问题转化为在小集合中的搜索。 【哈希表时间复杂度】 虽然哈希表一直在和冲突做斗争但在实际使用过程中我们认为哈希表的冲突率是不高的冲突个数是可控的也就是每个桶中的链表的长度是一个常数所以通常意义下我们认为哈希表的插入/删除/查找时间复杂度是 O(1) 。 总结
1、Map 和 Set 是一种专门用来进行动态搜索的数据结构。
2、Map 中存储的就是 Key-Value而 Set 中只存储了 Key。
3、不同关键字通过相同哈希函数计算出相同的哈希地址这种现象称为哈希冲突 (哈希碰撞)。
4、开散列中每个桶中放的都是发生哈希冲突的元素。
5、哈希表的插入/删除/查找时间复杂度是 O(1)。
