数据结构结尾部分
二叉搜索树
二叉搜索树可以是一个空树，或者就是具备以下性质的树：若其左子树不为空时，则左子树上所有节点的值都小于根节点的值；若其右子树不为空时，则右子树上所有节点的值都小于根节点的值；而且它的左右子树也满足这种性质。
查找key是否在二叉搜索树中
public TreeNode search(int key){TreeNode cur=root;while (cur!=null){if (cur.valkey){cur=cur.left;}else {return cur;}}return null;} 插入元素
public boolean insert(int key){TreeNode node=new TreeNode(key);if (root==null){root=node;return true;}TreeNode cur=root;TreeNode parent=null;if (cur.val>key){parent=cur;cur=cur.left;}else if (cur.val删除关键字为key的节点
public void remove(int key) {TreeNode cur = root;TreeNode parent = null;while (cur != null) {if(cur.val < key) {parent = cur;cur = cur.right;}else if(cur.val > key) {parent = cur;cur = cur.left;}else {//找到了 就要开始删除了removeNode(cur,parent);return;}}}private void removeNode(TreeNode cur, TreeNode parent) {if(cur.left == null) {if(cur == root) {root = root.right;}else if(cur == parent.left) {parent.left = cur.right;}else {parent.right = cur.right;}}else if(cur.right == null) {if(cur == root) {root = root.left;}else if(cur == parent.left){parent.left = cur.left;}else {parent.right = cur.left;}}else {TreeNode targetParent = cur;TreeNode target = cur.right;while (target.left != null) {targetParent = target;target = target.left;}cur.val = target.val;//分两种情况if(targetParent.left == target) {targetParent.left = target.right;}else {targetParent.right = target.right;}}}Map和Set
Map中存储的就是key-value的键值对，Set中只存储了Key。
Map是一个接口类，该类没有继承自Collection，该类中存储的是
Map的底层结构是TreeMap的时候
Map map=new TreeMap<>();map.put("do",12);map.put("baekhyun",5);map.put("krystal",2);System.out.println(map);Set> entrySet=map.entrySet();for (Map.Entry entry:entrySet) {System.out.println("key:"+entry.getKey()+" value:"+entry.getValue());}//返回 key 对应的 valueSystem.out.println(map.get("baekhyun"));//返回 key 对应的 value，key 不存在，返回默认值System.out.println(map.getOrDefault("baekhyunkrystal", 521));//返回所有 key 的不重复集合Set set=map.keySet();System.out.println(set);//返回所有 value 的可重复集合Collection collection=map.values();System.out.println(collection); | Map底层结构 | TreeMap | HashMap |
| 底层结构 | 红黑树 | 哈希桶 |
| 插入/删除/查找时间复杂度 | O（ log₂N） | O（1） |
| 是否有序 | 关于Key有序 | 无序 |
| 线程安全 | 不安全 | 不安全 |
| 插入/删除/查找区别 | 需要进行元素比较 | 通过哈希函数计算哈希地址 |
| 比较与覆写 | Key必须能够比较，否则会抛出ClassCastException异常 | 自定义类型需要覆写 equals 和hashCode方法 |
| 应用场景 | 需要 Key 有序场景下 | Key 是否有序不关心，需要更高的时间性能 |
Set不存储重复的元素
Set最大的功能就是对集合中的元素进行去重；Set 中只存储了 key ，并且要求 key 一定要唯一练习
//删除重复的元素public static void func1(int[] array){Set set=new HashSet<>();for (int i = 0; i < array.length; i++) {set.add(array[i]);}System.out.println(set);}//找到第一个重复的数据public static int func2(int[] array){Set set=new HashSet<>();for (int i = 0; i < array.length; i++) {if (!set.contains(array[i])){set.add(array[i]);}else {return array[i];}}return -1;}//每个数据重复的次数public static void func3(int[] array){Map map=new HashMap<>();for (int i = 0; i < array.length; i++) {int key=array[i];if (map.get(key)==null){map.put(key,1);}else {int val=map.get(key);map.put(key,val+1);}}System.out.println(map);}public static void main(String[] args) {int[] array=new int[100000];Random random=new Random();for (int i = 0; i < array.length; i++) {array[i]=random.nextInt(5000);}//func1(array);System.out.println(func2(array));func3(array);} | Set 底层结构 | TreeSet | HashSet |
| 底层结构 | 红黑树 | 哈希桶 |
| 插入 / 删除 / 查找时间复杂度 | O（ log₂N） | O（1） |
| 是否有序 | 关于Key有序 | 不一定有序 |
| 线程安全 | 不安全 | buanq |
| 插入 / 删除 / 查找区别 | 按照红黑树的特性来进行插入和删除 | 1. 先计算 key 哈希地址 2. 然后进行插入和删除 |
| 比较与覆写 | key 必须能够比较，否则会抛出ClassCastException异常 | 自定义类型需要覆写 equals 和hashCode方法 |
| 应用场景 | 需要 Key 有序场景下 | Key 是否有序不关心，需要更高的时间性能 |
哈希冲突的避免
由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的，这就导致一 个问题， 冲突的发生是必然的，但我们能做的应该是尽量的降低冲突率。闭散列
当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以
把key 存放到冲突位置中的 “ 下一个 ” 空位置中去 线性探测、二次探测
开散列
首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集 合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。public class HashBuck {static class Node{public int key;public int val;public Node next;public Node(int key, int val) {this.key = key;this.val = val;}}public Node[] array;public int usedSize;//记录 当前哈希桶当中 有效数据的个数//默认的负载因子public static final float DEFAULT_LOAD_FACTOR = 0.75F;public void put(int key, int val){Node node=new Node(key,val);int index=key%array.length;Node cur=array[index];while (cur!=null){if (cur.key==key){cur.val=val;return;}cur=cur.next;}//头插法node.next=array[index];array[index]=node;usedSize++;//检查负载因子if(loadFactor() >= DEFAULT_LOAD_FACTOR) {//进行 扩容grow();}}private float loadFactor() {return usedSize*1.0f / array.length;}private void grow() {Node[] newArray = new Node[2* array.length];//重新的哈希/*** 1. 遍历数组的每个元素的链表* 2. 每遍历到一个节点，就重新哈希 key % len* 3. 进行头插法*/for (int i = 0; i < array.length; i++) {Node cur = array[i];while (cur != null) {Node curNext = cur.next;//找到新的位置int index = cur.key % newArray.length;cur.next = newArray[index];newArray[index] = cur;//这样写对吗？//cur = cur.next;cur = curNext;}}this.array = newArray;}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;}
}反射、枚举以及lambda表达式
反射
在运行状态中，能动态的获取当前类或者当前对象的信息这样的机制。
获得Class对象有三种方式
//1.使用Class.forName（“类的全路径名）；静态方法
Class c1 = Class.forName("reflectdemo.Student");
//2.使用.class方法
Student student=new Student();
Class c2=student.getClass();
//3.使用类对象的getClass()方法
Class c3=Student.class;
枚举
将一个一个的具体固定的对象在类中实例化列举出来的类就叫作枚举类。这些在枚举类中实例化的
对象一定是具体固定的。枚举类是一种常量的集合，可以理解为：枚举属于一种特殊的类，里面只
包含一组特定的对象。
Enum 常用方法
1、对象.name 方法
该方法返回对象的名字
2、对象.ordinal 方法
该方法返回枚举对象在枚举类中定义的次序/编号，在枚举类中所有对象的编号从0开始
3、类名.values 方法
该方法以数组的形式返回枚举类中定义的所有枚举对象
public enum TestEnum {RED("red",2),BLACK("BLACK",3),GREEN("GREEN",4),WHITE("WHITE",5);public String color;public int ordinal;TestEnum(String color,int ordinal) {this.color = color;this.ordinal = ordinal;}public static void main(String[] args) {//拿到枚举实例BLACKTestEnum testEnum = TestEnum.BLACK;//拿到枚举实例REDTestEnum testEnum21 = TestEnum.RED;System.out.println(testEnum.compareTo(testEnum21));System.out.println(BLACK.compareTo(RED));System.out.println(RED.compareTo(BLACK));}public static void main2(String[] args) {TestEnum[] testEnums = TestEnum.values();for (int i = 0; i < testEnums.length; i++) {System.out.println(testEnums[i]+" 序号："+testEnums[i].ordinal());}System.out.println("============");TestEnum testEnum = TestEnum.valueOf("GREEN");System.out.println(testEnum);}public static void main1(String[] args) {TestEnum testEnum2 = TestEnum.BLACK;switch (testEnum2) {case RED:System.out.println("red");break;case BLACK:System.out.println("black");break;case WHITE:System.out.println("WHITE");break;case GREEN:System.out.println("green");break;default:break;}}Lambda表达式
//无返回值无参数
@FunctionalInterface
interface NoParameterNoReturn {void test();
}//无返回值一个参数
@FunctionalInterface
interface OneParameterNoReturn {void test(int a);
}//无返回值多个参数
@FunctionalInterface
interface MoreParameterNoReturn {void test(int a,int b);
}//有返回值无参数
@FunctionalInterface
interface NoParameterReturn {int test();
}//有返回值一个参数
@FunctionalInterface
interface OneParameterReturn {int test(int a);
}//有返回值多参数
@FunctionalInterface
interface MoreParameterReturn {int test(int a,int b);
}public class Test {public static void main(String[] args) {MoreParameterReturn moreParameterReturn=(x,y)->x+y;System.out.println(moreParameterReturn.test(12, 24));}public static void main5(String[] args) {OneParameterReturn oneParameterReturn=x->2*x;System.out.println(oneParameterReturn.test(12));}public static void main4(String[] args) {NoParameterReturn noParameterReturn=()->{return 10;};int ret= noParameterReturn.test();System.out.println(ret);NoParameterReturn noParameterReturn1=()->10;int ret1= noParameterReturn.test();System.out.println(ret1);}public static void main3(String[] args) {MoreParameterNoReturn moreParameterNoReturn=(a,b)->{System.out.println(a+b);};moreParameterNoReturn.test(12,54);MoreParameterNoReturn moreParameterNoReturn1=(a,b)-> System.out.println(a*b);moreParameterNoReturn1.test(2,3);}public static void main2(String[] args) {OneParameterNoReturn oneParameterNoReturn=(x)->{System.out.println(x);};oneParameterNoReturn.test(12);System.out.println("简化：");OneParameterNoReturn oneParameterNoReturn1=x-> System.out.println(x);oneParameterNoReturn1.test(54);//方法引用OneParameterNoReturn oneParameterNoReturn2=System.out::println;oneParameterNoReturn2.test(23);}public static void main1(String[] args) {NoParameterNoReturn noParameterNoReturn=new NoParameterNoReturn() {@Overridepublic void test() {System.out.println("测试一下");}};noParameterNoReturn.test();NoParameterNoReturn noParameterNoReturn1=()->{System.out.println("测试一下1");};noParameterNoReturn1.test();NoParameterNoReturn noParameterNoReturn2=()->{System.out.println("测试一下1");System.out.println("测试一下2");};noParameterNoReturn2.test();}
}本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！