数据结构-map和set

一，二叉搜索树
搜索树的特点：
若它的左子树不为空，则左子树上所有节点的值都小于根节点的值 。若它的右子树不为空，则右子树上所有节点的值都大于根节点的值 。它的左右子树也分别为二叉搜索树
实现一棵搜索树（链式储存）：

1. class BinarySearchTree{
2.     public TreeNode root;
3.     static class TreeNode{
4.         public int val;
5.         public TreeNode left;
6.         public TreeNode right;
7.         public TreeNode(int val){
8.             this.val=val;
9.         }
10.     }
11. }

复制代码

1，搜索：
我们先将根赋值给cur。将目标k与cur举行比较，如果k便是cur的值，那么找到了，返回节点。如果k大于cur，那么要找的只可能在cur的右边，所以cur=cur.right。反之，如果k小于cur，那么要找的只可能在cur的左边，所以cur=cur.left。再次重复上述判断，直到cur便是空，循环结束。二叉树搜索树中没有目标值。

1. public TreeNode search(int k){
2.     TreeNode cur=root;
3.     while (cur!=null){
4.         if (cur.val<k){
5.             cur=cur.right;
6.         } else if (cur.val>k) {
7.             cur=cur.left;
8.         }else {
9.             return cur;
10.         }
11.     }
12.     return null;
14. }

复制代码

2，插入：
先找到要放的位置。我们先将根赋值给cur。将parent界说为null。将val与cur的值举行比较，如果val便是cur的值，已经有重复的节点了，所以这次不做存储，直接return。先用parent将cur记载一下，然后如果val大于cur，那么要放在cur的右边，所以cur=cur.right。反之，先用parent将cur记载一下，如果val小于cur，那么要放在cur的左边，所以cur=cur.left。再次重复上述判断，直到cur便是空，循环结束。找到的目标要存放的位置为parent的左边大概右边，这时要将val与parent值举行比较，如果val大于parent，则把节点放到parent右边，反之，放到左边。

1. public void insert(int val){
2.     TreeNode node=new TreeNode(val);
3.     if (root==null){
4.         root=node;
5.         return;
6.     }
7.     TreeNode cur=root;
8.     TreeNode parent=null;
9.     while (cur!=null){
10.         parent=cur;
11.         if (cur.val>val){
12.             cur=cur.left;
13.         }else if (cur.val<val){
14.             cur=cur.right;
15.         }else {
16.             return;
17.         }
18.     }
19.     if (val> parent.val){
20.         parent.right=node;
21.     }else {
22.         parent.left=node;
23.     }
25. }

复制代码

3，删除：
要先找到要删除的目标，思绪与查找相似，唯一差别的是需要记载cur的父亲节点。找到之后我们判断cur的左边是否为空，如果为空可分为三种情况，
（1）cur就是根结点：所以删除根结点，root=cur.right;
（2）cur在parent的左边：所以parent.left=cur.right;
（3）cur在parent的右边：所以parent.right=cur.right;

再判断cur的右边有否为空，同样分为三种情况，
（1）cur就是根结点：所以删除根结点，root=cur.right;
（2）cur在parent的左边：所以parent.left=cur.left;
（3）cur在parent的右边：所以parent.right=cur.left;

其余情况：
需要我们再设置两个变量，分别为target=cur.right，targetP=cur。我们需要在cur为根的子树中找到可以代替cur的节点，即只比cur大一点的节点，大概只比cur小一点的节点，也就是cur的右树的最左树。大概是左树的最右树。我们这里以比cur大一点的节点举例。
我们找到cur大一点的节点为target（不再举行赘述），将target的值赋给cur。然后判断target是否为targetp的左树，如果是：targetP.left=target.right;如果target为targetp的右树（则说明一开始targe的左边就为null），那么：targetP.right=target.right。

-------------------------------------------------------

1. private void removeNode(TreeNode parent,TreeNode cur){
2.       if (cur.left==null){
3.           if (cur==root){
4.               root=cur.right;
5.           } else if (cur==parent.left) {
6.               parent.left=cur.right;
7.           }else {
8.               parent.right=cur.right;
9.           }
10.       } else if (cur.right==null) {
11.           if (cur==root){
12.               root=cur.left;
13.           } else if (cur==parent.left) {
14.               parent.left=cur.left;
15.           }else {
16.               parent.right=cur.left;
17.           }
19.       }else {
20.           TreeNode target=cur.right;
21.           TreeNode targetP=cur;
22.           while (target.left!=null){
23.               targetP=target;
24.               target=target.left;
25.           }
26.           cur.val=target.val;
27.           if (target==targetP.left){
28.               targetP.left=target.right;
29.           }else {
30.               targetP.right=target.right;
31.           }
32.       }
33. }

复制代码

二，map和set
Map和set是一种专门用来举行搜索的容器大概数据结构，其搜索的效率与其详细的实例化子类有关。
1，模子：
（1） 纯 key 模子 ，比如：快速查找一个单词是否在词典中
（2）Key-Value 模子 ，比如：统计文件中每个单词出现的次数
2，map
Map是一个接口类，该类没有继承自Collection，该类中存储的是结构的键值对，并且K一定是唯一的，不能重复。

3，map的常见方法：
（1）V get(Object key) -》返回 key 对应的 value。如果key重复了，就会更新val值
（2）V getOrDefault(Object key, V defaultValue) -》返回 key 对应的 value，key 不存在，返回默认值
（3）V put(K key, V value) -》设置 key 对应的 value
（4）V remove(Object key) -》删除 key 对应的映射关系
（5）Set keySet() -》返回所有 key 的不重复集合
（6）Collection values() -》返回所有 value 的可重复集合
（7）Set<Map.Entry <K, V>> entrySet() -》返回所有的 key-value 映射关系
（8）boolean containsKey(Object key)  -》判断是否包含
（9）key boolean containsValue(Object value)  -》判断是否包含 value

1. Map<String ,String> map=new TreeMap<>();
2. map.put("及时雨","松江");
3. map.put("及时雨","松江2");//如果k重复了，就会更新val值
4. map.put("齐天大圣","孙悟空");
5. String val=map.get("齐天大圣");
6. System.out.println(val);
7. String val2=map.getOrDefault("齐天大圣2","hehe");
8. System.out.println(val2);//如果k不存在，则返回默认值
9. // System.out.println(map.remove("齐天大圣"));
10. Set<String> set=map.keySet();//把所有k放到set里面
11. System.out.println(set);
12. Set<Map.Entry<String,String>> entries=map.entrySet();
13. System.out.println(entries);
14. for (Map.Entry<String,String> enter:entries){
15.     //System.out.print(enter+" ");
16.     System.out.println("k:"+enter.getKey()+" val"+enter.getValue());
17. }

复制代码

注意：
（1） Map是一个接口，不能直接实例化对象，如果要实例化对象只能实例化实在现类TreeMap大概HashMap
（2）Map中存放键值对的Key是唯一的，value是可以重复的
（3）在TreeMap中插入键值对时，key不能为空
（4）Map中键值对的Key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然后再来举行重新插入
（5）往treemap中存储元素的时候，可以一定是可比较的
（6）TreeMap和HashMap的区别

4，set
Set与Map主要的差别有两点：Set是继承自Collection的接口类，Set中只存储了Key。

5,set的主要方法：
（1）boolean add(E e) 添加元素，但重复元素不会被添加乐成
（2）void clear() 清空集合
（3）boolean contains(Object o) 判断 o 是否在集合中
（4）boolean remove(Object o) 删除集合中的 o
（5）int size() 返回set中元素的个数
（6）boolean isEmpty() 检测set是否为空，空返回true，否则返回false
（7）Object[] toArray() 将set中的元素转换为数组返回
（8）boolean containsAll(Collection<?> c) 集合c中的元素是否在set中全部存在，是返回true，否则返回false
（9）boolean addAll(Collection<?extends E> c) 将集合c中的元素添加到set中，可以达到去重的效果
（10）Iterator<E> iterator() 返回迭代器

1. Set<String> set=new TreeSet<>();
2. set.add("abc");
3. set.add("hell0");
4. set.add("abc");//set中不能存储重复的元素
5. System.out.println(set);
6. Iterator<String> it=set .iterator();
7. while (it.hasNext()){
8.     System.out.println(it.next());
9. }

复制代码

注意：
（1）Set是继承自Collection的一个接口类
（2）Set中只存储了key，并且要求key一定要唯一
（3）TreeSet的底层是使用Map来实现的，其使用key与Object的一个默认对象作为键值对插入到Map中的
（4）Set最大的功能就是对集合中的元素举行去重
（5）TreeSet中不能插入null的key，HashSet可以
（6）Set中的Key不能修改，如果要修改，先将原来的删除掉，然后再重新插入
（7）. TreeSet和HashSet的区别

6，哈希表
一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间可以或许创建一一映射的关系，那么在查找时通过该函数可以很快 找到该元素。
该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表
1，哈希冲突：差别关键字通过雷同哈 希哈数计算出雷同的哈希地点，该种征象称为哈希冲突或哈希碰撞。
冲突的发生是一定的，但我们能做的应该是尽量的降低冲突率
2，冲突避免方式
（1）哈希函数设计（尽量均匀分布）
（2）负载因子调节（官方：loadFactor=0.75）
解决哈希冲突两种常见的方法是：闭散列和开散列
闭散列：
也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中一定还有空位置，那么可以 把key存放到冲突位置中的“下一个” 空位置中去。
1. 线性探测：
比如上面的场景，现在需要插入元素，先通过哈希函数计算哈希地点，但是该位置已经放了其他元素，即发生哈希冲突。 线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止
2. 二次探测：
线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着今后逐个去找，因此二次探测为了避免该题目，找下一个空位置的方法为：Hi = (Ho + i^2)% m,其中：i = 1,2,3…
研究表明：当表的长度为质数且表装载因子a不高出0.5时，新的表项一定可以或许插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的题目。在搜索时可以不思量表装满的情况，但在插入时必须确保表的装载因子a不高出0.5，如果超出必须思量增容。 因此：比散列最大的缺陷就是空间使用率比较低，这也是哈希的缺陷。
开散列/哈希桶:
开散列法又叫链地点法(开链法)，首先对关键码集合用散列函数计算散列地点，具有雷同地点的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。