JAVA学习5

链表的基本单元是节点；

单向链表每一个节点都有两个属性:①下一个节点的内存地址，②存储的数据；

单向链表

链表的优点：因为在内存空间上地址不连续，所以链表的增删不会导致大量元素位移，随机增删元素效率较高；缺点：查询效率较低，每一次查找都需要从头部节点开始遍历；

如果在实际业务中随机增删较多的情况下，建议用linkedList存储数据；

在实际开发中添加元素一般是往末尾添加，所以ArrayList使用较多；

双向链表

linkedList没有初始容量，内部变量first与last初始值为null;

实际开发中，不管是linkedList还是ArrayList,写代码的时候不需要关心具体是哪个集合，因为是面向接口编程，调用的方法都是接口中的方法；

表示底层用了数组
//ArrayList l = new ArrayList<>();
//表示底层用了双向链表
linkedList l = new linkedList<>();

l.add("aaa");
l.add("aaa1");
l.add("aaa22");

for (int i = 0; i < l.size(); i++) {
    System.out.println(l.get(i));
}

底层是数组，初始容量是10，扩容后是原容量的2倍；

Vector所以方法都带synchronized修饰，是线程同步的，是线程安全的，效率较低，使用较少了；

Vector l = new Vector();

l.add("aaa");
l.add("aaa1");
l.add("aaa22");

Iterator it = l.iterator();

while (it.hasNext()) {
     System.out.println(it.next());
}

使用泛型Movie表示，集合中只能存储Movie类型的数据；

用泛型来指定集合中存储的数据类型，使用泛型之后集合中的数据类型更加统一了；

List l = new ArrayList();
l.add(new LoveMovie());
l.add(new WarMovie());

// 表示迭代器迭代的是Movie类型
Iterator it = l.iterator();

while (it.hasNext()) {
     //使用泛型后，不需要强制类型转换了，每次迭代器返回的都是Movie类型
     it.next().seeMovie();
}

泛型语法机制，只是在程序编译阶段起作用，只是给编译器参考的，运行阶段没用；

泛型的优点：集合中的元素类型统一，如果迭代器使用泛型，就不需要强制类型转换了；

泛型的缺点：集合中存储的元素缺乏多样性；

大多数业务中，集合的类型是统一的，所以泛型特性被认可；

自定义泛型

public class Movie {
    public String name;

    public void leave(E e) {
        System.out.println(e);
    }
}

public static void main(String[] args) {
    Movie m = new Movie<>();
    m.leave("aaa");
}

java源码中常用E(element)和T(type)自定义泛型；

在JDK8之后推出了自动类型推断机制，又称为钻石表达式；

//JDK8之后，后面的ArrayList的泛型内容可以不写
List l = new ArrayList<>();

Map和Collection没有继承关系；

Map集合以key-value的形式存储数据；

        key和value都是引用数据类型；

        key和value都是存储对象的内存地址；

        key起主导作用，value是key的附属品;

Map的常用方法:

        Map m = new HashMap<>();
        // 向Map集合添加键值对
        m.put(1, "无间道");
        m.put(2003, "阿凡达");
        m.put(33, "八佰");

        // 通过key获取value值
        String s = m.get(2003);
        System.out.println(s);

        // 获取键值对的数量
        System.out.println(m.size());

        // 通过key删除key-value
        m.remove(1);

        // 判断是否包含某个key
        // contains方法底层调用的是equals，所以自定义类型需要重写equals方法
        System.out.println(m.containsKey(33));

        // 判断是否包含某个value
        System.out.println(m.containsValue(new String("八佰")));

        // 获取所以value
        Collection v = m.values();
        for (String str : v) {
            System.out.println(str);
        }

        // 清空集合
        m.clear();

        // 判断是否为空
        System.out.println(m.isEmpty());

遍历Map

        Map m = new HashMap<>();
        // 向Map集合添加键值对
        m.put(1, "无间道");
        m.put(2003, "阿凡达");
        m.put(33, "八佰");

        Set keys = m.keySet();
        Iterator it = keys.iterator();
        //方式一
        while (it.hasNext()) {
            Integer key = it.next();
            System.out.println(m.get(key));
        }
        //方式二
        for (Integer integer : keys) {
            System.out.println(m.get(integer));
        }

方式三

        Set> s = m.entrySet();

        Iterator> it2 = s.iterator();

        while (it2.hasNext()) {
            Map.Entry node = it2.next();
            Integer key = node.getKey();
            String val = node.getValue();
            System.out.println(key + "--" + val);
        }

        //或者
        //此方式不必先获取key再通过key获取value,所以效率较高，适合大数据量遍历
        for (Map.Entry entry : s) {
            System.out.println(entry.getKey() + "---" + entry.getValue());
        }

HashMap集合底层是哈希表/散列表的数据结构；

哈希表是一个数组和单向链表的结合体；

数组：在增删数据的时候效率较低，在查询的时候效率较高；

单向链表：在增删数据的时候效率较高，在查询的时候效率较低；

哈希表将以上两种数据结构融合在一起，充分发挥他们各自的优点；

类似：数组里面是一个个链表；

 源码解析

//哈希表是一维数组，数组的每一个元素是一个单向链表，是数组和单向链表的结合体；
transient Node[] table;

static class Node implements Map.Entry {
        //hash值是key的hashCode()的执行结果，hash值通过hash函数/算法，可以转换存储成数组的下标
        final int hash;    
        final K key;    //存储到map集合的key
        V value;    //存储到map集合的value
        Node next;    //下一个节点的内存地址

        Node(int hash, K key, V value, Node next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
}

hashMap的key部分的特点是无序不可重复的：因为节点不一定挂载到哪一个单向链表上，所以是无序的，equals方法判断两个key如果相同，那么新的value会覆盖旧的value，所以是不可重复的；

由于hashMap集合中的key部分的元素其实就是放到了hashSet集合中了，所以hashSet集合中的元素也需要同时重写hashCode和equals方法；

假设所有的haseCode方法返回一个固定值，那么会导致底层哈希表变成了单向链表，哈希表hashMap使用不当时无法发挥性能；这种情况我们称为散列分布不均匀；

如果有100个元素，分布在10个单向链表，每个单向链表有10个元素，这是最好的，是散列分布均匀的；

如果所有的hashCode方法返回的值都不同，那么就会导致哈希表的底层变成了一维数组，没有链表的概念了，这种情况也是散列分布不均匀的；

散列分布均匀需要重写hashCode方法时有一定的技巧；

hashMap底层数组的容量是16，默认加载因子是0.75，就是当hashMap底层数组的容量达到75%的时候，数组开始扩容，扩容之后的容量是原容量的2倍；

hashMap的初始化容量必须是2的n次方(2,4,8,16...),这是官方推荐的，这是为了达到散列均匀，提高hashMap集合的存储效率，所必须的；

向map集合中存和取都是先调用hashCode方法再调用equals方法，equals有可能调用，有可能不调用；

put(k,v)中，k的hashCode方法返回哈希值，哈希值通过哈希算法转成数组下标，如果数组下标不存在，则直接添加节点,equals方法不执行；

get(k)中，k的hashCode方法返回哈希值，哈希值通过哈希算法转成数组下标，如果数组下标没有元素，则返回null，equals方法不执行；

如果一个类的equals方法重写了，那么它的hashCode方法必须重写，并且如果equals方法返回的是true,那么两个对象hashCode方法返回值必须一样；

equals方法返回true,表示两个对象相同，在同一个单向链表上比较，那么对于同一个单向链表上的节点来说，他们的哈希值是相同的，所以hashCode方法返回的值也应该相同；

终极结论：放在hashMap集合的key部分的元素与hashSet集合的元素，他们的hashCode方法和equals方法必须重写；

JDK8之后，hashMap里面的单向链表中的元素如果超过8个，单向链表这种数据结构会变成红黑树数据结构，当红黑树的元素少于6个，则红黑树会变成单向链表数据结构；

//参考源码
static final int TREEIFY_THRESHOLD = 8;

static final int UNTREEIFY_THRESHOLD = 6;

这种方式也是为了提高检索效率，二叉树的检索会再次缩小检索范围，提高效率；

对于哈希表数据结构来说:

如果o1和o2的哈希值相同，一定是同一个单向链表上，当然，如果o1和o2的哈希值不同，但由于哈希算法执行结束之后转换的数组下标可能相同，此时会发生哈希碰撞

hashTable的key和value都不能是null,否则报空指针异常；

hashTable方法都带有synchronized修饰符，是线程安全的；

现在线程安全有其他的解决方案，这个hashTable对线程安全的处理，导致效率低下，使用较少了；

hashTable与hashMap一样，底层都是哈希表数据结构；

hashTable的初始化容量是11，默认加载因子是0.75；

hashTable的扩容是原容量*2+1；