文章目录一、二叉搜索树1.1 二叉搜索树的定义1.2 核心操作1查找2插入3删除1.3 性能瓶颈与改进方向二、Map接口Key-Value键值对容器2.1 Map的特性2.2 内部类Map.EntryK,V2.3 Map的常用方法2.4 TreeMap与HashMap的区别三、Set接口无重复元素的集合3.1 Set的特性3.2 Set的常用方法3.3 TreeSet与HashSet的区别四、哈希表HashMap与HashSet的底层4.1 哈希表的核心思想4.2 哈希冲突Hash Collision1冲突的定义2冲突的避免① 哈希函数设计原则常用哈希函数② 负载因子调节重点3冲突的解决① 闭散列开放定址法② 开散列链地址法重点4.3 哈希表的实现简化版HashMap4.4 哈希表与Java类集的关联一、二叉搜索树1.1 二叉搜索树的定义二叉搜索树是一种具有排序特性的二叉树满足以下规则若左子树不为空左子树上所有节点的值均小于根节点的值若右子树不为空右子树上所有节点的值均大于根节点的值左右子树也分别为二叉搜索树。对于数组{5,3,4,1,7,8,2,6,0,9}构建的二叉搜索树如下5 / \ 3 7 / \ / \ 1 4 6 8 / \ \ 0 2 91.2 核心操作1查找查找逻辑遵循左小右大原则若根节点值等于目标值返回当前节点若目标值小于根节点值在左子树中查找若目标值大于根节点值在右子树中查找。publicTreeNodesearch(intkey){TreeNodecurroot;while(cur!null){if(cur.valkey)curcur.right;elseif(cur.valkey)curcur.left;elsereturncur;}returnnull;}时间复杂度取决于树的高度最优为完全二叉树的O(log₂N)最差为单支树的O(N)。2插入若树为空直接将新节点作为根节点若树非空按查找逻辑遍历找到插入位置父节点的左/右子树为空处若插入值小于父节点值作为左子节点插入否则作为右子节点插入。publicvoidinsert(intkey){if(rootnull){rootnewTreeNode(key);return;}TreeNodecurroot;TreeNodeparentroot;while(cur!null){if(cur.valkey){parentcur;curcur.left;}elseif(cur.valkey){parentcur;curcur.right;}else{return;}}if(parent.valkey)parent.leftnewTreeNode(key);elseparent.rightnewTreeNode(key);}3删除删除需分三种情况处理保证删除后树的结构仍满足二叉搜索树规则情况1待删除节点cur无左子树若cur是根节点根节点更新为cur的右子树否则将父节点parent的对应指针左/右指向cur的右子树。情况2待删除节点cur无右子树逻辑与情况1对称将父节点的对应指针指向cur的左子树。情况3待删除节点cur左右子树均存在采用“替换法”在cur的右子树中找到中序遍历的第一个节点即右子树中最小节点称为后继节点用该节点的值覆盖cur的值再删除后继节点后继节点必满足情况1或情况2。publicvoidremove(intkey){TreeNodecurroot;TreeNodeparentnull;while(cur!null){if(cur.valkey){parentcur;curcur.right;}elseif(cur.valkey){parentcur;curcur.left;}else{removeNode(parent,cur);break;}}}privatevoidremoveNode(TreeNodeparent,TreeNodecur){//情况1if(cur.leftnull){if(curroot)rootcur.right;elseif(curparent.left)parent.leftcur.right;elseif(curparent.right)parent.rightcur.right;}//情况2elseif(cur.rightnull){if(curroot)rootcur.left;elseif(curparent.left)parent.leftcur.left;elseif(curparent.right)parent.rightcur.left;}//情况3else{TreeNodetmpParentcur;TreeNodetmpcur.right;//找到右树的最小节点while(tmp.left!null){tmpParenttmp;tmptmp.left;}cur.valtmp.val;//删除右树最小节点if(tmpParent.lefttmp)tmpParent.lefttmp.right;elseif(tmpParent.righttmp)tmpParent.righttmp.right;}}1.3 性能瓶颈与改进方向二叉搜索树的性能依赖于树的结构若插入顺序有序如1,2,3,4会退化为单支树此时查找/插入/删除的时间复杂度变为O(N)完全失去优势。改进方案使用平衡二叉搜索树如红黑树通过颜色规则和旋转操作维持树的平衡确保最坏情况下的时间复杂度仍为O(log₂N)。这也是TreeMap和TreeSet的底层实现。二、Map接口Key-Value键值对容器Map是Java中存储键值对Key-Value的核心接口其设计目标是支持高效的键查找、插入和删除。2.1 Map的特性不继承自Collection接口独立成为顶层接口Key唯一不可重复Value可重复支持Key的快速查找底层实现决定查找效率常用实现类TreeMap红黑树实现、HashMap哈希表实现。Map没有实现Iterable实现的类不可以通过迭代器进行遍历。如果需要遍历可以先调用entrySet()返回到Set中再遍历SetMap.EntryString,IntegerentrySettreeMap.entrySet();for(Map.EntryString,Integerentry:entrySet){System.out.println(key: entry.getKey() value: entry.getValue());}2.2 内部类Map.EntryK,VMap通过内部类Map.Entry存储单个键值对提供了键值对的访问方法方法功能K getKey()返回当前Entry的KeyV getValue()返回当前Entry的ValueV setValue(V value)修改当前Entry的Value返回旧值注意Map.Entry不提供修改Key的方法若需修改Key需先删除原键值对再重新插入。2.3 Map的常用方法方法功能描述V get(Object key)根据Key获取ValueKey不存在返回nullV getOrDefault(Object key, V defaultValue)根据Key获取ValueKey不存在返回默认值V put(K key, V value)插入键值对Key已存在则覆盖Value返回旧ValueV remove(Object key)删除Key对应的键值对返回删除的ValueSetK keySet()返回所有Key的集合不可重复CollectionV values()返回所有Value的集合可重复SetMap.EntryK,V entrySet()返回所有键值对的集合boolean containsKey(Object key)判断是否包含指定Keyboolean containsValue(Object value)判断是否包含指定Value2.4 TreeMap与HashMap的区别对比维度TreeMapHashMap底层结构红黑树平衡二叉搜索树哈希桶数组链表/红黑树时间复杂度插入/删除/查找O(log₂N)插入/删除/查找O(1)平均情况有序性按Key自然排序或自定义排序无序Key限制不可为null需支持比较实现Comparable或提供Comparator可为null仅允许一个nullKeyValue限制可为null可为null允许多个nullValue线程安全不安全不安全适用场景需要Key有序的场景如排序统计无需有序追求高效读写的场景三、Set接口无重复元素的集合Set接口继承自Collection核心特性是“存储无重复的Key”底层实现依赖于Map将Key作为Map的KeyValue使用一个默认空对象填充。3.1 Set的特性仅存储Key不存储ValueKey唯一重复元素插入失败Set实现了Iterable实现的类可以通过迭代器进行遍历。TreeSet不可以插入null的key而HashSet可以。常用实现类TreeSet红黑树实现、HashSet哈希表实现、LinkedHashSet哈希表双向链表保留插入顺序。3.2 Set的常用方法方法功能描述boolean add(E e)插入元素重复元素返回falseboolean contains(Object o)判断是否包含指定元素boolean remove(Object o)删除指定元素成功返回trueint size()返回元素个数IteratorE iterator()返回迭代器用于遍历元素void clear()清空集合3.3 TreeSet与HashSet的区别对比维度TreeSetHashSet底层结构红黑树哈希桶数组链表/红黑树时间复杂度插入/删除/查找O(log₂N)插入/删除/查找O(1)平均情况有序性按Key自然排序无序LinkedHashSet保留插入顺序Key限制不可为null需支持比较可为null仅允许一个null去重逻辑基于比较器Comparable/Comparator基于hashCode()和equals()适用场景需要有序去重的场景无需有序追求高效去重的场景四、哈希表HashMap与HashSet的底层哈希表Hash Table是一种“键值对映射”的数据结构通过哈希函数将Key映射到存储地址实现O(1)级别的高效读写是HashMap和HashSet的底层实现。4.1 哈希表的核心思想理想的搜索场景是“无需比较直接定位”。哈希表通过以下逻辑实现哈希函数Hash Function将Key转换为存储地址如hash(key) key % 数组长度插入元素通过哈希函数计算地址将键值对存入该地址查找元素通过哈希函数计算地址直接访问该地址获取元素。示例对于数据集合{1,4,5,6,7,9}哈希函数为hash(key) key % 10数组长度为10存储结果如下数组索引0123456789存储元素-1--4567-94.2 哈希冲突Hash Collision1冲突的定义当两个不同的Key通过哈希函数计算出相同的存储地址时称为哈希冲突。例如“”Key4和Key444%10444%104会映射到同一地址。冲突是必然存在的——因为哈希表的数组长度有限而Key的范围可能无限无法避免不同Key映射到同一地址。我们能做的是“尽量降低冲突率”。2冲突的避免冲突避免的核心是“优化哈希函数”和“调节负载因子”。① 哈希函数设计原则定义域覆盖所有Key值域在[0, 数组长度-1]之间计算结果均匀分布减少冲突计算效率高简单易实现。常用哈希函数函数类型实现逻辑适用场景直接定制法Hash(key) A*key B线性函数Key范围小且连续如年龄除留余数法Hash(key) key % pp为接近数组长度的质数通用场景HashMap采用类似逻辑平方取中法对Key平方后取中间几位未知Key分布Key位数较少折叠法将Key分割为若干部分叠加求和后取模Key位数较多如手机号② 负载因子调节重点负载因子Load Factor定义负载因子 已存储元素个数 / 数组长度。负载因子越大数组越满冲突率越高负载因子越小数组越空空间利用率越低。结论负载因子需控制在合理范围java中HashMap默认0.75。当负载因子超过阈值时会触发数组扩容通常扩容为原来的2倍从而降低负载因子减少冲突。3冲突的解决当冲突发生时需通过特定方式处理常用方案有“闭散列”和“开散列”。① 闭散列开放定址法逻辑当地址冲突时在数组中寻找下一个空位置存储元素。线性探测从冲突地址开始依次向后查找空位置如Key44冲突后查找索引5、6、7、8找到空位置8存储缺陷容易导致“数据堆积”冲突元素集中在某一区域降低查找效率二次探测改进线性探测查找逻辑为H i (H0 ± i²) % 数组长度i1,2,3…分散冲突元素但空间利用率较低负载因子需≤0.5。② 开散列链地址法重点逻辑数组的每个位置称为“桶”存储一个链表数组长度超过64且链表长度超过8转为红黑树冲突的元素被加入同一个桶的链表中。示例Key4和Key44冲突后都存入索引4的桶中形成链表数组索引01234…存储元素-1--4→44→null…开散列的优势空间利用率高无需预留空位置冲突处理简单仅在桶内链表操作性能稳定HashMap采用此方案当链表长度超过8时转为红黑树进一步优化查找效率。4.3 哈希表的实现简化版HashMap以下是基于开散列链地址法的简化版哈希表实现包含put插入、get查找和resize扩容操作publicclassHashBuck{//键值对staticclassNode{publicintkey;publicintval;publicNodenext;publicNode(intkey,intval){this.keykey;this.valval;}}//哈希数组publicNode[]arrnewNode[10];//已存节点个数publicintusedSize;//负载因子阈值publicstaticfinaldoubleDEFAULT_LOAD_FACTOR0.75f;//插入publicvoidput(intkey,intval){intindexkey%arr.length;Nodecurarr[index];while(cur!null){//key存在则替换valif(cur.keykey){cur.valval;return;}curcur.next;}//key不存在,新建节点NodenewNodenewNode(key,val);//头插法newNode.nextarr[index];arr[index]newNode;usedSize;//检查负载因子if(doLoadFactor()DEFAULT_LOAD_FACTOR){resize();}}//扩容privatevoidresize(){Node[]newArrnewNode[arr.length*2];for(inti0;iarr.length;i){Nodecurarr[i];while(cur!null){intindexcur.key%newArr.length;//记录cur的下一个节点防止后面修改cur.next后找不到原来的节点NodecurNextcur.next;//头插法cur.nextnewArr[index];newArr[index]cur;curcurNext;}}arrnewArr;}//计算负载因子privatedoubledoLoadFactor(){returnusedSize*1.0/arr.length;}//根据key获取valpublicintgetValue(intkey){intindexkey%arr.length;Nodecurarr[index];while(cur!null){if(cur.keykey)returncur.val;curcur.next;}return-1;}}注意扩容不可以直接把原来的数组复制到新数组中因为哈希地址会随着数组长度改变必须遍历每一个元素重新分配地址。对于引用类型的数据重写hashCode()方法保证逻辑上认为相等的对象hashcode也相等再调用hashcode()得到这个对象的hashcode再计算哈希地址。判断key是否相等时不可以用来判断而是要调用重写的equals()方法。例如importjava.util.Objects;publicclassStudent{intid;Stringname;Overridepublicbooleanequals(Objecto){if(onull||getClass()!o.getClass())returnfalse;Studentstudent(Student)o;returnidstudent.idObjects.equals(name,student.name);}OverridepublicinthashCode(){//当id和name相等时hashcode也相等returnObjects.hash(id,name);}}4.4 哈希表与Java类集的关联HashMap/HashSet的底层实现均基于哈希表开散列HashSet本质是“Key为元素、Value为默认空对象的HashMap”冲突处理JDK8中当桶内链表长度超过8时自动转为红黑树当长度小于6时转回链表平衡时间和空间效率自定义Key的要求若使用自定义类作为HashMap的Key或HashSet的元素必须覆写hashCode()和equals()方法且需满足equals()返回true的两个对象hashCode()必须相等hashCode()相等的两个对象equals()不一定返回true避免误判为相同元素。