亚马逊雨林是怎么形成的,seo如何优化网站,网站开发维护成本,分析电子商务网站建设需求教案List常用实现类 List集合常用的实现类有3个 #xff0c; ArrayList , LinkedList , Vector ArrayList 类似于我们之前的ArrayBox 底层使用数组存储元素#xff0c; 插入删除的效率低#xff0c;检索的效率高 当底层数组存储容量不足时#xff0c;会进行扩容#xff0c;…List常用实现类 List集合常用的实现类有3个 ArrayList , LinkedList , Vector ArrayList 类似于我们之前的ArrayBox 底层使用数组存储元素 插入删除的效率低检索的效率高 当底层数组存储容量不足时会进行扩容每次扩容都是原数组的1.5倍 使用无参构造器创建ArrayList集合时首先提供的是一个默认0长度的数组防止内存资源浪费 第一次add元素的时候会创建一个10个长度的数组
Vector 我们在开发中已经不怎么使用了 Vector是ArrayList早期版本1.0 起初有自己的一套api方法后来与ArrayList实现了相同的List接口 Vector也是使用数组的结构存储 Vector早期版本线程同步的安全性高但效率低。 ArrayList是非线程同步的安全性低但效率高 (想到StringBuilder和StringBuffer) Vector底层数组容量不足时会按照原容量的2倍扩容 ArrayList按照原容量1.5扩容 Vector在创建对象时可以指定扩容增量每次扩容时会按照指定的增量扩容 ArrayList只能1.5倍扩容
LinkedList 类似于我们之前封装的LinkedBox 底层使用双向链表存储元素插入删除效率高检索效率低 LinkedList还提供了一组与头尾元素操作相关的方法。
2 Set常用实现类 常用的实现类有2个 HashSet TreeSet 底层用来存储元素的都是对应的Map相当于只存储了map中的key而没有value
HashSet 底层使用的是HashMap存储 向set中存储一个元素就相当于向map中存储了一个key 这个value是什么呢 是 null 么。 不是 。 底层的map如果key重复会返回之前的value。 如果key不重复返回null 对于set而言返回null说明key不重复说明保存成功。 反之说明key重复保存失败 如果用null作为value就无法判断保存是否成功 需要让value值是一个具体的对象。 但每次创建一个新对象又浪费空间。所以用唯一的对象作为value值
public boolean add(E e) {return map.put(e, PRESENT)null;
} TreeSet TreeSet底层是通过TreeMap集合存储。 存储的key是自然有序的有大小顺序 集合存储的类对象的这就要求存入TreeSet中的元素TreeMap中的key要可以比较大小 自身比较(Comparable)或提供第三方比较器(Comparator) 使用无参构造器创建TreeSet时要求存储的元素必须自身可以比较 要么就使用可以传递第三方比较器的Tree构造方法
public TreeSet(Comparator comparator){} TreeSet在存储第一个元素的时候也需要保证元素是可以比较大小的。
3 Map常用实现类 Map常用的实现类有3个 HashMap TreeMap Hashtable
HashMap 底层使用数组 链表结构存储元素。jdk1.8之后变成了数组 链表 or 红黑树 存储元素 hash的存储特点是单一元素的 快存 和 快取 每次存储的元素key都会通过一个hash算法计算出该元素在数组中存储的位置 有可能第1个元素被计算出存储在5位置。 第2个元素被计算出存储2位置。使得存储位置是零散的 是根据元素的什么信息进行位置的hash计算 是根据元素的hashcode值。 每一个元素都会有一个hashcode值我们通过调用hashcode方法来获得。 Object中有一个hashcode方法是一个native修饰的方法表示该方法是由jvmc/c语言实现的 是由jvm为对象提供的一个尽可能唯一的数值。可以当成地址使用不是内存地址 对象的hashcode不是与生俱来的当第一次调用hashcode方法时才会生成hashcodeJOL验证 hashcode值的作用就是为hash存储结构来计算存储位置的。 hashcode方法可以被重写重写原则是 equals相等 hashcode也相等。反之无所谓。 hash碰撞 两个不同的对象通过hash计算后算出了相同的存储位置 两个对象都需要存储会在当前位置形成一个链表 扩展hashmap保存元素时的那些事 当发生hash碰撞时会用新节点与当前位置链表中的每一个节点进行比较 有相等的hash相等equals相等。同一个keykey去重value覆盖 不相等就将新元素的节点添加到链表最后 对于hash碰撞时当前的hashMap底层使用的时链表的尾插法 jdk1.7时发生hash碰撞采用的是头插法 头超法在多线程时会有问题 jdk1.8之后HashMap底层使用数组 链表 或 红黑树。为什么用到树呢 防止链表过长影响hash效率。当链表长度超过8时就会尝试转换成红黑树了。 如果数组长度64 , 会优先2倍扩容 如果数组长度64就会实现链表到红黑树的转化 HashMap底层数组的长度问题 尽管HashMap提供了有参构造器可以指定数组的初始容量但最终都会处理成的2的次幂 也就是说 hashmap底层的数组无论如何其长度都是2的次幂数
//cap 10
static final int tableSizeFor(int cap) {//n 9//16个0 1000 0000 0000 0000int n cap - 1;//n n | n1 ;//n 28个0 1001 | 28个0 0100//n 28个0 1101//1000 0101 0010 1001 | 0100 0010 1001 0100//1100 0111 1011 1101n | n 1;//1101 | 0011//28个0 1111 1000016//11111 10000032//1100 0111 1011 1101 | 0011 0001 1110 1111//1111 0111 1111 1111n | n 2;// 1111 | 0000//1111 0111 1111 1111 | 0000 1111 0111 1111 n | n 4;n | n 8;n | n 16;//x个0 y个1return (n 0) ? 1 : (n MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1;
} hashmap底层有很多的计算都是基于位运算的 通过hash计算元素的存储位置 jdk早期版本通过除法取模计算最终的存储位置 hash101,length6 , 101%65 数组扩容
Hashtable Hashtable 与HashMap作用相同也是hash结构适合快存 快取 区别 Hashtable早期版本线程同步安全性高效率低 HashMap非线程同步安全性低效率高 Hashtable中的key和value不能为null HashMap中的key和value可以为null
TreeMap 底层使用的是红黑树存储元素是BST树的一种特殊形式 我们暂时只需要了解BST 是一个二叉树一个节点有左右两个子节点和一个父节点 节点间存储在大小关系左枝节点 父节点 右枝节点 存储 第一个节点必然就是最开始的节点我们称为根节点 第二个数据添加时会从根节点开始依次进行大小比较 如果与根节点key相同说明重复key取重value覆盖 如果与根节点key不相同根据大小如果小于根节点的key向左枝找位置否则反之 接着会与左枝节点比较相等取重不等继续比较大小 直到某一个节点的左枝或右枝为null说明找到了要存放的位置完成节点链接即可。 遍历 二叉树有3种遍历方式 前序遍历中序遍历后序遍历 以父节点为基准 父 左 右 前序 左 父 右 中序 左 右 父 后续 BST - AVL - 红黑树 4 位运算符
运算符都有哪些呢 算数运算符 赋值运算符比较运算符逻辑运算符条件运算符位运算符 位运算符的特点 对二进制进行运算的 按位运算的 位运算符包括 按位与|按位或^按位异或~按位取反 左移 , 无符号右移 , 带符号右移
