August 2020

一.Map与Set1.1 HashMapHashMap<key,value>的存储结构为hash表，其节点为具有key与value属性的Entry类型。其get(key)方式为先将key值转化为HashCode，再利用HashCode找到其在哈希表中对应的Entry节点，从而获取value值，因此map的get(key)方法实质上是对key的查找。 由于Map不提供迭代器，因此需自行实现，推荐实现方式为调用 entrySet() 函数，函数返回Set<Entry<?,?>>类型集合，并利用Set的迭代器进行遍历 当Map内装入的类型为自定义类型时需要重写hashCode()方法与equals()方法(IDE可自动生成)，原因在于需要基于自定义类的内部属性生成hash值，从而利用hash值判断需要存储的位置，而equals()方法则用于判断两个节点是否相同，若没有重写则java默认hash值为对象的存储地址的转化值，判断两个对象是否相等的方法也为判断二者地址是否相同。 1.2 HashSetHashSet底层即为HashMap，创建一个HashSet实际上为创建了一个HashMap。HashSet内部定义一个空对象PRESENT，当调用add方法插入元素a时即在HashMap中插入元素(a,PRESENT)，当调用HashSet的迭代器时即由HashMap调用keySet().iterator()返回key集合的迭代器 2.1 TreeMapTreeMap结构为红黑树(自平衡二叉查找树)，其中树的每一个节点类型为Entry 类型，由于红黑树基于比较对节点进行查找，因此需要实现内部比较器(Comparable)或外部比较器(Comparator)，当插入与查询时使用比较器判断下一个比较节点从而找到对应的节点 2.2 TreeSetTreeSet底层为TreeMap，其中插入查询等操作均为调用TreeMap相关函数，故不再赘述 二.List1.ArrayListArrayList底层为数组，其函数基本为对数组基本操作的封装，其自动扩容方式为当判断当前数组大小不足时产生一个新数组，并将原数组内容copy至新数组。基于其底层为数组结构，ArrayList基于索引的查找速度最快，而基于内容的查找速度最慢，且在指定位置增加或删除元素速度均较慢 2.LinkedListLinkedList底层为双向链表，因此查找速度较慢，但增加与删除元素速度较快 三.总结 四.结尾关于java 容器的知识来自于B站视频 https://www.bilibili.com/video/BV1eW411R7jx?p=1