旅游网站效果图,小程序二维码怎么获取,外贸开发软件有哪些,新乡谷雨网络公司做的网站怎么样目录 一.二叉搜索树1.1 概念1.2 二叉搜索树的简单实现 二.Map2.1 概念2.2 Map常用方法2.3 Map使用注意点2.4 TreeMap和HashMap的区别2.5 HashMap底层知识点 三.Set3.1 概念3.2 Set常用方法3.3 Set使用注意点3.4 TreeSet与HashSet的区别 四.哈希表4.1 概念4.2 哈希冲突与避免4.3… 目录 一.二叉搜索树1.1 概念1.2 二叉搜索树的简单实现 二.Map2.1 概念2.2 Map常用方法2.3 Map使用注意点2.4 TreeMap和HashMap的区别2.5 HashMap底层知识点 三.Set3.1 概念3.2 Set常用方法3.3 Set使用注意点3.4 TreeSet与HashSet的区别 四.哈希表4.1 概念4.2 哈希冲突与避免4.3 冲突解决4.3.1 闭散列4.3.2 开散列(哈希桶)4.3.3 哈希桶的简单实现 一.二叉搜索树
1.1 概念
二叉搜索树又称二叉排序树其是一棵空树或者具有以下性质的二叉树
如果树的左子树不为空则左子树上的所有结点的值都小于根节点的值如果树的右子树不为空则右子树上的所有结点的值都大于根节点的值树的左右子树都分别为一棵二叉搜索树
1.2 二叉搜索树的简单实现
public class BinarySearchTree {static class TreeNode {public int val;public TreeNode left;public TreeNode right;public TreeNode(int val) {this.val val;}}public TreeNode root;public boolean search(int val) { //查找值为val的结点TreeNode cur root;while (cur ! null) {if (cur.val val) { //当前结点的值小于valcur cur.right; //在其右子树查找} else if (cur.val val) { //当前结点的值大于valcur cur.left; //在其左子树寻找} else { //当前结点的值等于val,查找成功return true;}}return false;}public void insert(int val) { // 插入值为val的结点// 1.按照二叉搜索树的性质,查找到要插入的结点// 2.插入新结点if (root null) {root new TreeNode(val);return;}TreeNode parent null;TreeNode cur root;while (cur ! null) {if (cur.val val) {parent cur;cur cur.right;} else if (cur.val val) {parent cur;cur cur.left;} else {return;}}TreeNode newNode new TreeNode(val);if (parent.val val) {parent.left newNode;} else {parent.right newNode;}}public void remove(int val) { //删除值为val的结点TreeNode parent null;TreeNode cur root;while (cur ! null) {if (cur.val val) {parent cur;cur cur.right;} else if (cur.val val) {parent cur;cur cur.left;} else {// parent:待删除节点的父结点// cur:待删除结点removeNode(parent, cur);}}}private void removeNode(TreeNode parent, TreeNode cur) {if (cur.left null) { //cur.left为空的情况if (cur root) { //cur是rootroot cur.right;} else if (cur parent.left) { //cur不是root,cur是parent的左子结点parent.left cur.right;} else { //cur不是root,cur是parent的右子结点parent.right cur.right;}} else if (cur.right null) { //cur.right为空的情况(与cur.left为空的情况相同)if (cur root) {root cur.left;} else if (cur parent.left) {parent.left cur.left;} else {parent.right cur.left;}} else { //cur.left与cur.right都不为空的情况//使用替换法删除,在cur结点的右子树中寻找值最小的结点来替换cur的值TreeNode t cur.right; //值最小的结点TreeNode tp cur; //值最小结点的父结点while (t.left ! null) {tp t;t t.left;}cur.val t.val;if (tp.left t) { //删除结点ttp.left t.right;} else {tp.right t.right;}}}
}二.Map
2.1 概念
Map和Set是一种专门用来进行搜索的数据结构一般把搜索的数据称为关键字(Key)与关键字对应的称为值(Value)。Map是一个接口类使用了Key-Value模型类中存储的是Key,Value键值对并且Key是唯一的不能重复。Map内部使用了Map.EntryK,V的内部类来存放Key,Value键值对的映射关系
2.2 Map常用方法
方法解释V get(Object key)返回key对应的valueV getOrDefault(Object key,V defaultValue)返回key对应的valuekey不存在则返回defaultValue(默认值)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使用注意点
Map是一个接口不能直接实例化对象如果要实例化对象只能实例化其实现类TreeMap或者HashMapMap中存放键值对的key是唯一的value是可以重复的在TreeMap中插入键值对时key不能为空否则会抛出NullPointerException(空指针)异常value可以为空HashMap的key和value都可以为空Map中的key可以全部分离出来存储到Set中进行访问Map中的value也可以全部分离出来存储到Collection的任意一个子集合中Map中键值对的key不能直接修改value可以修改如果要修改key只能将key删除掉再重新插入
2.4 TreeMap和HashMap的区别
MapTreeMapHashMap底层结构红黑树哈希桶插入/删除/查找时间复杂度O(log2N)O(1)是否有序关于key有序无序线程安全不安全不安全插入/删除/查找区别需要进行元素比较通过哈希函数计算哈希地址比较与覆写key必须能够比较否则会抛异常自定义类型需要覆写equals和hashCode方法应用场景需要key有序场景下不关心key是否有序有更高的时间性能需求
2.5 HashMap底层知识点
HashMap的最大容量为230当指定HashMap初始容量capacity时生成的HashMap的容量为最接近capacity的二次幂的值(例如指定容量为20实际容量为32指定容量为1000实际容量为1024)未指定HashMap初始容量时生成的HashMap默认容量为16HashMap扩容时为2倍扩容HashMap的put方法使用的是尾插法如果HashMap中存储数组长度64且各个桶中的单链表的长度8HashMap就会树化(单链表转变成红黑树)
三.Set
3.1 概念
Set也是一个接口类与Map不同Set使用的是纯Key模型类中只存储Key
3.2 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中全部存在boolean addAll(Collection? extends E c)将集合c中的元素添加到set中可达到去重的效果
3.3 Set使用注意点
Set是继承自Collection的一个接口类Set中只存储了key并且要求key唯一实现Set接口的常用类有TreeSet和HashSet还有LinkedHashSet(在HashSet的基础上维护了一个双向链表来记录元素的插入次序)TreeSet底层使用Map实现使用key与Object默认对象作为键值对插入到Map中与Map类似Set中的key也不能直接修改如果修改key要删除并重新插入TreeSet不能插入null的keyHashSet可以
3.4 TreeSet与HashSet的区别
SetTreeSetHashSet底层结构红黑树哈希桶插入/删除/查找时间复杂度O(log2N)O(1)是否有序关于key有序不一定有序线程安全不安全不安全插入/删除/查找区别按照红黑树的特性来进行插入删除计算key哈希地址再进行插入和删除比较与覆写key必须能够比较否则会抛出异常自定义类型需要覆写equals和hashCode方法应用场景需要key有序场景下不关心key是否有序有更高的时间性能需求
四.哈希表
4.1 概念
哈希表又称散列表是一种数据结构其通过哈希函数(散列函数)在元素的存储位置与关键码之间建立一一映射的关系从而实现快速的插入、搜索和删除操作 例如数据集合{1,5,9}哈希函数设置为hash(key)key%capacitycapacity为存储元素底层空间总大小 4.2 哈希冲突与避免
哈希冲突对于两个不同的关键字如果通过哈希函数计算出了相同的哈希地址这种现象称为哈希冲突 由于哈希表底层数组容量往往小于实际存储的关键字数量这就导致冲突的发生是必然的但是我们可以通过一些方法尽量降低冲突率。冲突避免的方法有
哈希函数设计引起哈希冲突的原理可能是哈希函数的设计不够合理常用哈希函数有直接定制法除留余数法平方取中法折叠法随机数法数学分析法等负载因子调节负载因子α填入表中的元素个数/哈希表的长度α越大表明填入表中的元素越多产生冲突的可能性就越大反之则α越小则填入表中元素越少产生冲突的可能性越小。想要降低冲突率就要降低负载因子由于哈希表中元素个数是不可变的我们可以通过调整哈希表中数组的大小来实现哈希冲突避免
4.3 冲突解决
解决哈希冲突的两种常见方法分别为闭散列和开散列
4.3.1 闭散列
闭散列也称开放定址法当发生哈希冲突时如果哈希表没有被装满说明在哈希表中还有空位置这时可以把key存放到冲突位置中的下一个空位置去下个空位置的具体寻找方法如下 9. 线性探测从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止 10. 二次探测线性探测会导致产生冲突的数据堆积在一起二次探测为了避免这个问题调整寻找下一个空位置的方法为(hash(key)i^2^)%capacity (其中i1,2,3,…)
4.3.2 开散列(哈希桶)
开散列又称链地址法对关键码集合用哈希函数计算哈希地址具有相同地址的关键码归属于同一个子集合每一个子集合称为一个桶各个桶中的元素通过一条单链表(长度突破大于一定阈值后转变为红黑树)连接起来每条链表的头结点存储在哈希表中。在Java中就使用了哈希桶这种方式来解决冲突
4.3.3 哈希桶的简单实现
public class HashBucketK, V {static class NodeK, V {K key;V val;NodeK, V next;public Node(K key, V val) {this.key key;this.val val;}}public NodeK, V[] array (NodeK, V[]) new Node[10];public int usedSize;public static final double LOAD_FACTOR 0.75; //负载因子public void put(K key, V val) {NodeK, V node new Node(key, val);int hash key.hashCode();int index hash % array.length;NodeK, V cur array[index];while (cur ! null) {if (cur.key.equals(key)) {cur.val val;return;}cur cur.next;}node.next array[index];array[index] node;usedSize;if (doLoadFactor() LOAD_FACTOR) {reSize();}}public void reSize() {NodeK, V[] newArray new Node[array.length * 2];for (int i 0; i array.length; i) {Node cur array[i];while (cur ! null) {int hash cur.key.hashCode();int index hash % newArray.length;Node curNext cur.next;cur.next newArray[index];newArray[index] cur;cur curNext;}}array newArray;}public double doLoadFactor() {return usedSize * 1.0 / array.length;}public V get(K key) {int hash key.hashCode();int index hash % array.length;NodeK, V cur array[index];while (cur ! null) {if (cur.key.equals(key)) {return cur.val;}cur cur.next;}return null;}
}
