本帖最后由 执迷不悟 于 2019-5-21 15:22 编辑
集合数据结构详解
链表LinkedList Java程序中所有的链表实际上都是双向链接的--即每个节点还存放着指向前驱节点的引用,链表不支持随机访问元素的方法,但是LinkedList提供了一个get方法,get方法做了优化,如果索引的大于size()/2那么它就会从尾部开始检索数据。 ListIterator类可以从前后两个方向遍历链表中的元素。
ArrayList和linkedLIst在用法上没有什么区别,但是在功能上是有区别的,linkedList经常用在增删操作比较多而查询操作很少的情况下,ArrayList则相反
Vector Vector类的所有方法都是同步的,可以由两个线程安全方法一个Vector对象,但是在由一个线程访问是会耗费大量的时间在处理同步操作上,建议在不需要同步的情况下使用ArrayList。
散列集 散列集可以快速的查找所需要的对象,它为每个对象计算一个整数,称为散列码。如果是自定义对象,就需要自己负责这个类的hashCode方法。
散列表用链表数组实现,每个列表被称为桶,如果要保存数据,需要先计算它的散列码例如:某个对象的散列码是76268,并且这个集合拥有128个桶,该对象保存在108号桶中(76268%128余108),这个时候会有两种情况,这个桶中没有其他元素,那么就会将数据插入这个链表的头部,还有一种情况就是这个桶被占满,这也是不可避免的,称为散列冲突,这种情况链表会从新扩容(原来个数的2次幂)并且将旧数据添加到新链表中,废弃旧链表, 桶也一样,有默认的装填因子(0.75默认值),如果列表中超过75%的位置已经填入了元素,那么散列就会在散列,个数是原来的两倍,将旧数据添加到新列表中废弃原来的列表。 Set集合没有重复元素,在使用add方法添加会先查找列表中是否存在当前对象,如果没有才会添加,hashSet实现了散列表集。
树集 TreeSet类与散列集很类型,它是一个有序的集合,如果将元素添加到集合中,它会自动排序,它的排序是树结构完成构建(当前使用的是红黑树),将一个元素添加到树种要比添加到散列中要慢很多,原因是如果树中包含了1000个元素,查找新元素的位置大约需要比较10次,而散列只需要计算hashCode,添加到桶中。
TreeSet是怎么保证元素循序的,使用的是comparable接口进行比较。
优先级队列PriortyQueue(); 元素可以按照任意循序插入,总是按照排序的循序进行检索,无论何时调用remode方法,总会获得当前队列优先级最低的元素,优先级使用一个高效的数据结构,称为堆,它是一个可以自我调整的二叉树,对树执行添加或删除可以让最小的元素移动的根部,而不必对元素进行排序,使用队列的典型就是任务调度,每当启动一个新的任务是,都将优先级最高的元素从队列中剔除,一般程序的默认优先级1是最大。
映射表是键/值对映射表,java中提供了两个通用的实现HashMap和treeMap 。 HashMap :是散列映射键值对集合,无序的。 TreeSet : 是树映射,是有序的。 通常来说HashMap比TreeSet添加删除要快,如果不需要排序选择散列好
专用集和映射表类1. 弱散列映射表 WeakJHashMap的出现是为了解决一个有趣的问题,如果一个值已经不再使用了,那么垃圾回收器为什么不回收他呢!遗憾的是垃圾回收器跟踪的是活跃的对象,只要映射表是活动的,那么它的桶也是活动的,垃圾回收器是无法回收的。 WeakHashMap使用了弱引用保存键,WeakReference对象会将引用保存到另一个对象中,垃圾回收器用一种特有的方法处理。 只要这个引用没有人使用了,垃圾回收器就会回收它,但是要将这个弱引用放入队列中,WeakHashMap会定期检查队列,一个弱引用进入队列就代表它已经没有人使用了。
2. 链接散列集和链接映射表
Jdk1.4新增了两个类:linkedHashSert和linkedHashMap,用来记录插入元素的顺序,链接散列映射表将用访问序列,而不是插入的顺序,每当调用get或put都会删除原来的位置,并且将元素放到链表的尾部,这个操作只会元素在链表中的位置,不会影响散列中的桶,有一个好处是可以将访问频率高的元素放到内存中,而反问频率第的从数据库访问,linkedHashMap有个一子类覆盖他的removeEldestEntry()可以实现。
3. 枚举集与映射表用的少不做研究
4. 标识散列映射表 Jdk1.4还增加了一个特殊的类:IdentityHashMap,在这个类中键的散列值不是使用HashCode计算的,而是使用System.identityHashCode计算,这是Object。HashCode方法根据对象的内存地址来计算,在对两个对象进行比较的时候用的是==而不是equals,可以用来跟中每个对象的遍历状况。
|