1.数组
1.1 特点:底层连续,有索引,增删慢,查询快,长度不可变
2.链表
2.1 特点:无索引,增删快,查询慢
2.2 链表的分类:
1.单链表
2.双向链表
比单向链表有遍历优势,可以判断要查找的元素靠近头还是靠近尾
3.循环链表
4.链表有大量对头尾的操作
3.HashSet 不能存储重复元素理论 (n - 1) & hash 就是计算索引的方法
1.当存储元素时,会首先调用其hashCode 方法,会根据hashCode 方法去判断到底应该存储在
数组上的哪个位置上,如果这个位置上没有元素,那么直接存储
如果有元素,则进行eqauls 方法比较
eqauls 比较结果 相同,如果相同, 不存
如果不同,则挂在数组上
2.LinkedHashSet 有序的Set集合(去重,保证顺序 了解)
3.1集合的体系结构
单列集合
在jdk1.5 以前 Collection 父类
jdk1.5 以后 迭代器接口
两大体系
第一大体系
List(有序,可重复)
ArryaList : 底层是一个数组-> 查询快,有索引,底层连续(?),增删慢 ,长度固定
LinkedList(不强制要求大家记住他的api): 底层是一个双向链表 -> 双向链表 遍历效率可能高于单向链表 可以判断你要查找的元素是靠近头,还是靠近尾
add
addFirst
addLast
removeFirst
removeLast
第二大体系
Set(无序,不可重复)
HashSet(重要 : HashSet 不能重复的原因)
1.首先计算要存储元素的hashCode 值,通过hashCode 值和 数组长度 一起计算出来对应的
数组索引,如果数组索引上没有元素-->直接存储
2.如果有调用eqauls 方法
2.1 相等 :不存
2.2 不相等:存
LinkedHashSet
TreeSet
4.TreeSet 原理 (左中右原则)
TreeSet : 可以排序 ,不可重复
ts.add(对象)
有两种可以告诉treeSet 排序的规则的方式
1.比较器排序
2.自然排序 调用无参构造方法
5. hashCode 方法 32 位 二进制数,其中二进制的最高位是表示正负而不是表示值的
最高位是1 ,就是一个负数 最高位如果是个0 ,就是一个正数 (常识)
以int 方式来返回的对应的值(在Object类中是通过内存地址值计算出来)
在String类中是通过内容计算
6.面试重点(目前阶段很难)
hash冲突 指的是不同的hashCode 值所对应的元素索引在数组中一样
hash冲突算法: 就是为了解决hash冲突
HashSet
public HashSet() {
map = new HashMap<>();
}
// HashSet 实际上在借HashMap
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
HashMap
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//在存储元素时,首先调用了存储元素的的 hash方法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
option1 : (h = key.hashCode()) ^ (h >>> 16);
N * name + H* age -->hashCode
10 20 --> 30
20 10 --> 30
15 15 --> 30
01111111 & 1 & 同1得 1 不同得0
确保 n 是一个偶数 n- 1 就一定是一个奇数
option2 : (n - 1) & hash (尽可能多的位数参与到运算)
101010101010
000000 & 同1得 1 不同得0
------------------
----》 0
末尾數 : 有可能是0 ,儅hashCode 为0 时,得出的结果是 0
,有可能是1 ,儅hashCode 为1 时,得出来结果是1
|
|