目录1搜索树2哈希表3注意点一搜索树1前提引入可以通过这张表看出set和map分别都有通过红黑树或者哈希表来实现的我们先从红黑树来讲起红黑树的底层就是搜索树我们先自己从自己创建的搜索树开始2概念可以是一颗空树或者具有这些性质左边的都比根结点要小右边都比根结点要大3方法的实现1查询//查找 public static TreeNode search(TreeNode root,int key){ if (rootnull){ return null; } TreeNode curroot; while (cur!null){ if (keycur.val){ curcur.right; }else if (cur.valkey){ return cur; }else { curcur.left; } } return null; }2增加元素//增加元素 public static void insert(TreeNode root,int key){ if (rootnull){ rootnew TreeNode(key); } TreeNode nodenew TreeNode(key); TreeNode curroot; TreeNode parentnull; while (cur!null){ if (keycur.val){ parentcur; curcur.right; }else if (cur.valkey){ return; }else { parentcur; curcur.left; } } if (parent.valkey){ parent.leftnode; }else if (parent.valkey){ parent.rightnode; } }3删除元素//删除 public static void remove(TreeNode root,int key){ if (rootnull){ return; } TreeNode curroot; TreeNode parentnull; //先要找到cur的位置在进行删除 while (cur!null){ if (key cur.val){ parentcur; curcur.right; }else if (keycur.val){ removecur(parent,cur); return; }else{ parentcur; curcur.left; } } } private static void removecur(TreeNode parent, TreeNode cur) { //核心就是要让变的部分等于cur.right if (cur.leftnull){ //cur为root if (curroot){ rootcur.right; }else if (curparent.left){ parent.leftcur.right; }else if (curparent.right){ parent.rightcur.right; } }//核心就是要让变的部分等于cur.left else if (cur.rightnull){ if (curroot){ rootcur.left; }else if (curparent.left){ parent.leftcur.left; }else if (curparent.right){ parent.rightcur.left; } }//左右都不为空的情况 //我们选择替换-让右边的最左树替换掉cur else { TreeNode targetcur.right; TreeNode targetparentcur; while (target.left!null){ targetparentparent; targettarget.left; } cur.valtarget.val; //也就是有左树 if (targettargetparent.left){ targetparent.lefttarget.right; }//没有左树只有右树那么target就是合适的替换人选 else { targetparent.righttarget.right; } } }4模型的介绍1K 模型只存 Key对应 Set容器里只存储关键字 Key没有配套的 value唯一作用判断某个 key 是否存在、自动去重。2KV 模型KeyValue 成对存储对应 Map容器存储一对数据 Key, Valuekey 唯一value 是 key 附带的业务信息通过 key 快速查找对应 value。map的存储是kv模型而set是纯k模型5treemap的方法实现1常见的方法方法名解释get(Object key)返回 key 对应的 valuegetOrDefault(Object key, V defaultValue)返回 key 对应的 valuekey 不存在返回默认值put(K key, V value)设置 key 对应的 valueremove(Object key)删除 key 对应的映射关系keySet()返回所有 key 的不重复集合values()返回所有 value 的可重复集合entrySet()返回所有的 key-value 映射关系containsKey(Object key)判断是否包含 keycontainsValue(Object value)判断是否包含 valueMap.Entrya,b是map内部类用来实现存放kv键值对映射关系的内部类下面的方法只有单个map.entry才能实现用set来点是可以发现没有对应的方法的因为我下面代码中的set已经表达的是一个map.entry的一个集合里面装着左右的map.entry,所以我们要拿出一个的话可以使用循环或者迭代器来实现方法解释K getKey()返回 entry 中的 keyV getValue()返回 entry 中的 valueV setValue(V value)将键值对中的 value 替换为指定 valuepublic static void main(String[] args) { MapString,Integer mapnew TreeMap(); map.put(ab,1); map.put(cd,2); map.put(ef,2); map.put(hello,5); SetString stringsmap.keySet(); System.out.println(strings); CollectionInteger collectionmap.values(); System.out.println(collection); SetMap.EntryString,Integer setmap.entrySet(); for (Map.EntryString, Integer entry : set) { System.out.println(key:entry.getKey() val:entry.getValue()); } //System.out.println(set); }2注意点1Map是⼀个接⼝不能直接实例化对象如果要实例化对象只能实例化其实现类TreeMap或者 ,HashMap2Map中存放键值对的Key是唯⼀的value是可以重复的3在TreeMap中插⼊键值对时key不能为空否则就会抛NullPointerException异常value可以为空。但是HashMap的key和value都可以为空。4Map中的Key可以全部分离出来存储到Set中来进⾏访问(因为Key不能重复)。5Map中的value可以全部分离出来存储在Collection的任何⼀个⼦集合中(value可能有重复)。6Map中键值对的Key不能直接修改value可以修改如果要修改key只能先将该key删除掉然后再来进⾏重新插⼊。6treeset的方法实现1常见的方法方法解释boolean add(E e)添加元素重复元素不会添加成功void clear()清空集合中所有元素boolean contains(Object o)判断元素 o 是否存在于集合IteratorE iterator()返回集合的迭代器用于遍历元素boolean remove(Object o)删除集合中的指定元素 oint size()返回集合内元素的总个数boolean isEmpty()判断集合是否为空空返回 true否则 falseObject[] toArray()将集合所有元素转为 Object 数组并返回boolean containsAll(Collection? c)判断传入集合 c 的所有元素是否都在当前 Set 中全部存在返回 trueboolean addAll(Collection? extends E c)将集合 c 全部元素添加进当前 Set自动去重public static void main(String[] args) { SetInteger setnew TreeSet(); set.add(2); set.remove(2); System.out.println(set.contains(2)); }2注意点1key要唯一2本质也就是treemaptreemap里面的key就是唯一的所以也就相当于是对应的但是treemap里面不是还有一个val项treeset默认传给一个object类二哈希表1概念我们通过哈希函数来放数据构造出来的结构称为哈希表我们常用的函数为key/capacity2冲突-避免面对上面说的冲突我们有避免和解决两种方法我们首先来讲避免1改善哈希函数面对不同的要求我们可以定制不同的哈希函数但是哈希函数一般我们都不会去改变他我们都是用的常用的也就是除留余数法key/capacity2调节负载因子散列表的负载因子填入表中的元素个数/散列表的长度负载因子和冲突率的函数图可以发现负载因子越大冲突率越大3冲突-解决解决我们一般有两种方法闭散列和开散列1闭散列1.1线性探测直接理解就是我们找到冲突后面的第一个空的元素填进去这样会导致冲突的元素都聚集在一起删除元素的时候会很麻烦因为如果我们要删除4的时候4下标的位置就空出来了当我们要找14的时候我们理应根据公式找到4下标但是我们会发现4下标是没有的所以这时候我们要删除的时候要标记一下那个下标是否已经被删除过了1.2二次探测这个方法比线性探测好一点但是元素多了也会导致矛盾元素的聚集也称为二次聚集也不太好2开散列重点开散列是我们重点要掌握的方法也俗称哈希桶3自己实现的哈希桶我们插入方法选择头插法1int类型public class HushBuck { static class Node{ //成员 public int key; public int val;//默认给999 public Node next; //构造方法 public Node(int key, int val) { this.key key; this.val val; } } public static Node[] array; public int usedSize; public static final double LOAD_FACTOR 0.75; public HushBuck(){ arraynew Node[10]; } public void push(int key, int val){ //确定下标 int indexkey%array.length; //更新val Node curarray[index]; while (cur!null){ if (cur.keykey){ cur.valval; return; } curcur.next; } //头插法 Node newNodenew Node(key, val); newNode.nextarray[index]; array[index]newNode; usedSize; //确认负载因子 if (usedSize*1.0/array.lengthLOAD_FACTOR){ //进行扩容并且重新哈希 resize(); } } private void resize(){ Node[] newArraynew Node[array.length*2]; for (int i 0; i array.length; i) { Node curarray[i]; while (cur!null){ int newIndexcur.key%newArray.length; Node curNcur.next; cur.nextnewArray[newIndex]; newArray[newIndex]cur; curcurN; } } arraynewArray; } public int get(int key){ int index key % array.length; Node cur array[index]; while (cur ! null) { if(cur.key key) { return cur.val; } cur cur.next; } return -1; } }2泛型public class HushBuck2 K,V{ static class NodeK,V{ //成员 public K key; public V val;//默认给999 public NodeK,V next; //构造方法 public Node(K key, V val) { this.key key; this.val val; } } public NodeK,V[] array; public int usedSize; public static final double LOAD_FACTOR 0.75; public HushBuck2(){ array(NodeK,V[]) new Node[10]; } public void push(K key, V val){ //确定下标 int hashkey.hashCode(); int indexhash%array.length; //更新val NodeK,V curarray[index]; while (cur!null){ if (cur.key.equals(key)){ cur.valval; return; } curcur.next; } //头插法 NodeK,V newNodenew NodeK,V(key, val); newNode.nextarray[index]; array[index]newNode; usedSize; //确认负载因子 if (usedSize*1.0/array.lengthLOAD_FACTOR){ //进行扩容并且重新哈希 resize(); } } private void resize(){ NodeK,V[] newArraynew Node[array.length*2]; for (NodeK, V kvNode : array) { NodeK, V cur kvNode; while (cur ! null) { int newIndex cur.key.hashCode() % newArray.length; NodeK, V curN cur.next; cur.next newArray[newIndex]; newArray[newIndex] cur; cur curN; } } arraynewArray; } public V get(K key){ int index key.hashCode() % array.length; NodeK,V cur array[index]; while (cur ! null) { if(cur.key.equals(key)) { return cur.val; } cur cur.next; } return null; } }三注意点1hashcode 和 equals 的区别当我们想加自己写的类的时候我们需要再类里面重写hashcode和equals方法保证一样的key哈希出来的值是一样的1equals负责判断内容相等2hashCode负责哈希容器快速分区3相等对象哈希值必须相同哈希值相同对象不一定相等4重写 equals一定要同步重写 hashCode否则哈希集合失效。2系统里的哈希方法只有在你put的时候才会第一次定义数组的长度才会分配内存调用不带参数的构造方法第一次的容量会是16用带参数传容量的构造方法会给到最接近你数字的二次幂比如你给15会给你16你要20会给你323当你扩容的时候记得要二次哈希
