黑马程序员技术交流社区

标题: 成都校区+集合 [打印本页]

作者: 廖廖落星辰 时间: 2019-4-18 13:59
标题: 成都校区+集合
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

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2