前言
由于太长,分成两篇记录,第一篇地址: 自自技术笔记(一)
JAVA数据结构相关笔记
hashmap
数组加链表存储,通过hash计算key值直接计算出链表在数组中的下标位置,再通过遍历链表判断hash查找value
二叉树其实就是链表的加强版
Java所有集合类型
- 1.ArrayList
- 2.LinkedList
- 3.Set 只允许一个null,且是无序的
- 4.TreeSet 有序的,访问遍历比较快,底层基于TreeMap,TreeSet根据其 compare() 和 compareTo() 的定义进行排序的有序容器。
- 5.TreeMap 红黑树数据结构,有序的,非同步
- 6.HashSet 散列法,底层基于Hashmap,无序
- 7.LinkedHashSet 有序的,底层基于HashMap
- 8.HashMap
- 9.HashTable
- 10.Vector 动态数组,线程安全
注意:共10个集合类!
Hashmap扩容机制
loadFactor默认0.75,扩容时要满足一下两个条件
1、 存放新值的时候当前已有元素的个数必须大于等于阈值
2、 存放新值的时候当前存放数据发生hash碰撞(当前key计算的hash值换算出来的数组下标位置已经存在值)
扩容时一般成倍扩容,自jdk1.8后引入新机制
当hash碰撞的链表长度超过默认的8时自动由链表变为红黑树
注意点:如果map触发扩容会重新计算每个数据的位置,所以应尽量避免扩容
ArrayList和LinkedList
- 1.arraylist是动态数组,适合使用下标随机访问,不适合添加删除,因为添加删除要移动数据。
- 2.linkedlist是双向链表数据结构,适合添加和删除,不适合通过下标随机访问,因为他是通过移动指针一个一个节点的去遍历
- 3.linkedlist插入和删除劲量操作第一个或者最后一个效率最高。
HashMap和HashTable
- 1.hashmap基本上可以代替haahtable了
- 2.hashtable是线程安全
- 3.hashtable的迭代器不同,当迭代过程中hashtable的值被修改时会报错
- 4.HashMap把Hashtable的contains方法去掉了,改成containsValue和containsKey,因为contains方法容易让人引起误解。
- 5.Hashtable继承自Dictionary类,而HashMap继承自AbstractMap类。但二者都实现了Map接口。