Java世界观：数据结构那些事儿，看完直接对线去

数据结构那些事儿

欧克吖~ 奈瑞Boby😉，
小菜猴呢，我最近在复习数据结构(ps:更像是在看Java集合…)，就整合一些大佬们优质的文章，省的大家再去搜索了。一起共勉，哪里不对，评论告诉我哦，瑞四百~

**

1.Java集合类大家族：

**

Collection

List

Arraylist： Object数组
Vector： Object数组
LinkedList： 双向循环链表

Set

HashSet（无序，唯一）：基于 HashMap 实现的，底层采用 HashMap 来保存元素
LinkedHashSet： LinkedHashSet 继承与 HashSet，并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的LinkedHashMap 其内部是基于 Hashmap 实现一样，不过还是有一点点区别的。
TreeSet（有序，唯一）： 红黑树(自平衡的排序二叉树。)

Map

HashMap： JDK1.8之前HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）.JDK1.8以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间
LinkedHashMap：LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。
HashTable： 数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的
TreeMap： 红黑树（自平衡的排序二叉树）

1.队列（queue）

FiFo：(12条消息) Java 集合深入理解（9）：Queue 队列_张拭心的博客 shixinzhang-CSDN博客_queue

2.set

特点： 不可重复：其实有点像map的“阉割版本”

HashSet 和 TreeSet 两员大将

在自定义参数使用treeset的的排序功能时：要记得实现Comparable Comparator的接口

package qiao.Conllection;

import java.util.Collection;
import java.util.Comparator;
import java.util.HashSet;
import java.util.TreeSet;

/** * @Classname Set * @Description set的使用 * @Date 2021/6/22 15:53 * @Created by 乔三 */
public class Set { 
   
    private int age;
    private  String name;
    public Set(){ 
   };

    public int getAge() { 
   
        return age;
    }

    public void setAge(int age) { 
   
        this.age = age;
    }

    public String getName() { 
   
        return name;
    }

    public void setName(String name) { 
   
        this.name = name;
    }

    public Set(int age, String name) { 
   
        this.age = age;
        this.name = name;
    }

    @Override
    public String toString() { 
   
        return "Set{" +
                "age=" + age +
                ", name='" + name + '\'' +
                '}';
    }

    public static void main(String[] args) { 
   
        TreeSet<Set> set=new TreeSet(new compare());
        set.add(new Set(15,"x"));
        set.add(new Set(16,"y"));
        set.add(new Set(11,"y"));
        System.out.println("输出结果： "+set);

        HashSet<Set> hashSet=new HashSet<>();
        hashSet.add(new Set(19,"xiaoming"));
        hashSet.add(new Set(14,"xming"));
        hashSet.add(new Set(14,"xming"));
        System.out.println("hashSet:"+hashSet);
    }
}
class  compare implements Comparator<Set> { 
   
    @Override
    public int compare(Set a, Set b) { 
   
        return a.getAge()-b.getAge();
    }
}

好玩的事情：

hashSet的会自动排序？

 java.util.Set<Integer> set1=new HashSet<>();
        set1.add(1);
        set1.add(5);//第一次添加
        set1.add(6);//第二次添加
        set1.add(-1);//第三次添加
        set1.add(2);
        System.out.println(set1);


输出结果：[-1, 1, 2, 5, 6]

答案： 其实不是！

众所周知吖：这个hashSet的底层是个hashMap ，导致这一现象的元凶就是 hashMap的hashCode();

 public int hashCode() { 
   
         return value;
    }

当你用integer时：这返回就是值本身 所以导致”看似是排序了 实际是个假像：“

激活成功教程方法：

直接加个随机值进去：只要够大： 就破掉了；

 Integer random=new Random(10).nextInt();

3.List

ArrayList:

ArrayList是List接口的大小可变数组的实现；ArrayList允许null元素；ArrayList的容量可以自动增长；ArrayList不是同步的；ArrayList的iterator和listIterator方法返回的迭代器是fail-fast的

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{ 
   
    private static final long serialVersionUID = 8683452581122892189L;

好玩的问题？

List接口：我们会出现这样一个疑问，在查看了ArrayList的父类AbstractList也实现了List接口，那为什么子类ArrayList还是去实现一遍呢？

答案：其实就是作者的一个“错误”~

RandomAccess 这是提高效率的接口：

Cloneable接口：实现了该接口，就可以使用Object.Clone()方法了。

Serializable接口：实现该序列化接口，表明该类可以被序列化，什么是序列化？简单的说，就是能够从类变成字节流传输，然后还能从字节流变成原来的类。

1.　　初始化为10；正常情况下会扩容1.5倍，特殊情况下（新扩展数组大小已经达到了最大值）则只取最大值。 四个add

核心代码：

private void grow(int minCapacity) { 
   
        // overflow-conscious code
        int oldCapacity = elementData.length;  //将扩充前的elementData大小给oldCapacity
        int newCapacity = oldCapacity + (oldCapacity >> 1);//newCapacity就是1.5倍的oldCapacity
        if (newCapacity - minCapacity < 0)//这句话就是适应于elementData就空数组的时候，length=0，那么oldCapacity=0，newCapacity=0，所以这个判断成立，在这里就是真正的初始化elementData的大小了，就是为10.前面的工作都是准备工作。
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)//如果newCapacity超过了最大的容量限制，就调用hugeCapacity，也就是将能给的最大值给newCapacity
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
    //新的容量大小已经确定好了，就copy数组，改变容量大小咯。
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

(oldCapacity >> 1); 就是向右移了一位： 相当于除以2；

源码分析：Java集合源码分析（一）ArrayList – LanceToBigData – 博客园 (cnblogs.com)

LinkList

LinkedList是一种可以在任何位置进行高效地插入和移除操作的有序序列，它是基于双向链表实现的。

通过API再次总结一下LinkedList的特性：

1）异步，也就是非线程安全

2）双向链表。由于实现了list和Deque接口，能够当作队列来使用。

链表：查询效率不高，但是插入和删除这种操作性能好。

3）是顺序存取结构（注意和随机存取结构两个概念搞清楚）

源码分析：

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

• AbstractSequentialList:顺序存储的基础 数组就是随机存储的

• Deque接口，Deque接口表示是一个双端队列，那么也意味着LinkedList是双端队列的一种实现，所以，基于双端队列的操作在LinkedList中全部有效。

• 应该注意到没有RandomAccess：那么就推荐使用iterator，在其中就有一个foreach，增强的for循环，其中原理也就是iterator，我们在使用的时候，使用foreach或者iterator都可以。

• foreach 底层就是个 iterator

  Iterator 和 ListIterator 有什么区别？

  Iterator 可以遍历 Set 和 List 集合，而 ListIterator 只能遍历 List。
  Iterator 只能单向遍历，而 ListIterator 可以双向遍历（向前/后遍历）。
  ListIterator 实现 Iterator 接口，然后添加了一些额外的功能，比如添加一个元素、替换一个元素、获取前面或后面元素的索引位置。

  linkedList底层有个继承ListIterator的 所以可以前后遍历

addAll()中的一个问题：

在addAll函数中，传入一个集合参数和插入位置，然后将集合转化为数组，然后再遍历数组，挨个添加数组的元素，

​ 但是问题来了，为什么要先转化为数组再进行遍历，而不是直接遍历集合呢？

从效果上两者是完全等价的，都可以达到遍历的效果。关于为什么要转化为数组的问题，我的思考如下：

1. 如果直接遍历集合的话，那么在遍历过程中需要插入元素，在堆上分配内存空间，修改指针域，这个过程中就会一直占用着这个集合，考虑正确同步的话，其他线程只能一直等待。

2. 如果转化为数组，只需要遍历集合，而遍历集合过程中不需要额外的操作，所以占用的时间相对是较短的，这样就利于其他线程尽快的使用这个集合。说白了，就是有利于提高多线程访问该集合的效率，尽可能短时间的阻塞。

1）linkedList本质上是一个双向链表，通过一个Node内部类实现的这种链表结构。
　　2）能存储null值
　　3）跟arrayList相比较，就真正的知道了，LinkedList在删除和增加等操作上性能好，而ArrayList在查询的性能上好
　　4）从源码中看，它不存在容量不足的情况
　　5）linkedList不光能够向前迭代，还能像后迭代，并且在迭代的过程中，可以修改值、添加值、还能移除值。
　　6）linkedList不光能当链表，还能当队列使用，这个就是因为实现了Deque接口。

[Java集合源码分析（二）Linkedlist – LanceToBigData – 博客园 (cnblogs.com)](

经典比较问题？

ArrayList LinkedList 两者的区别？

• ArrayList 数组实现 具有“数组”的特点和实现了 RandomAccess 接口 好找 不好改

• public E remove(int index) { 
       
          Objects.checkIndex(index, size);
          final Object[] es = elementData;//复制操作给一个新的数组
  
          @SuppressWarnings("unchecked") E oldValue = (E) es[index];
          fastRemove(es, index);//私有的快删方法
  
          return oldValue;
      }
  

• 缺点：改的时候，回进行复制操作，所以消耗性能

• LinkedList 具有“链表”和“队列”的特点。好改不好找 也没有实现RandomAccess 接口。直接“迭代器”

Set和List对比

Set：检索元素效率低下，删除和插入效率高，插入和删除不会引起元素位置改变。
List：和数组类似，List可以动态增长，查找元素效率高，插入删除元素效率低，因为会引起其他元素位置改变

hashMap

一个人支撑了java容器的”半壁江山！“

结构：1.8 分水岭：

之前：数组+链表

之后： 数组+链表+红黑树(记住：左小右大！)

基本属性的源码：

// 默认容量16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
 
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;    
 
// 默认负载因子0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f; 
 
// 链表节点转换红黑树节点的阈值, 9个节点转
static final int TREEIFY_THRESHOLD = 8; 
 
// 红黑树节点转换链表节点的阈值, 6个节点转
static final int UNTREEIFY_THRESHOLD = 6;   
 
// 转红黑树时, table的最小长度
static final int MIN_TREEIFY_CAPACITY = 64; 
 
// 链表节点, 继承自Entry
static class Node<K,V> implements Map.Entry<K,V> { 
     
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
 
    // ... ...
}
 
// 红黑树节点
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { 
   
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
   
    // ...
}

哈希经典：

// 代码1
static final int hash(Object key) { 
    // 计算key的hash值
    int h;
    // 1.先拿到key的hashCode值; 2.将hashCode的高16位参与运算
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 代码2
int n = tab.length;
// 将(tab.length - 1) 与 hash值进行&运算
int index = (n - 1) & hash;

考点：

1.return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

2.int index = (n – 1) & hash;

HashMap 和 Hashtable 的区别

HashMap 允许 key 和 value 为 null，Hashtable 不允许。
HashMap 的默认初始容量为 16，Hashtable 为 11。
HashMap 的扩容为原来的 2 倍，Hashtable 的扩容为原来的 2 倍加 1。
HashMap 是非线程安全的，Hashtable是线程安全的。
HashMap 的 hash 值重新计算过，Hashtable 直接使用 hashCode。
HashMap 去掉了 Hashtable 中的 contains 方法。
HashMap 继承自 AbstractMap 类，Hashtable 继承自 Dictionary 类。

总结

• HashMap 的底层是个 Node 数组（Node<K,V>[] table），在数组的具体索引位置，如果存在多个节点，则可能是以链表或红黑树的形式存在。

• 增加、删除、查找键值对时，定位到哈希桶数组的位置是很关键的一步，源码中是通过下面3个操作来完成这一步：1）拿到 key 的 hashCode 值；2）将 hashCode 的高位参与运算，重新计算 hash 值；3）将计算出来的 hash 值与 “table.length – 1” 进行 & 运算。

  考点：面试的“十万个为什么根源！”：

• 为什么：HashMap 的默认初始容量（capacity）是 16，capacity 必须为 2 的幂次方；默认负载因子（load factor）是 0.75；实际能存放的节点个数（threshold，即触发扩容的阈值）= capacity * load factor。

• HashMap 在触发扩容后，阈值会变为原来的 2 倍，并且会对所有节点进行重 hash 分布，重 hash 分布后节点的新分布位置只可能有两个：“原索引位置” 或 “原索引+oldCap位置”。例如 capacity 为16，索引位置 5 的节点扩容后，只可能分布在新表 “索引位置5” 和 “索引位置21（5+16）”。

• 导致 HashMap 扩容后，同一个索引位置的节点重 hash 最多分布在两个位置的根本原因是：1）table的长度始终为 2 的 n 次方；2）索引位置的计算方法为 “(table.length – 1) & hash”。HashMap 扩容是一个比较耗时的操作，定义 HashMap 时尽量给个接近的初始容量值。

• HashMap 有 threshold 属性和 loadFactor 属性，但是没有 capacity 属性。初始化时，如果传了初始化容量值，该值是存在 threshold 变量，并且 Node 数组是在第一次 put 时才会进行初始化，初始化时会将此时的 threshold 值作为新表的 capacity 值，然后用 capacity 和 loadFactor 计算新表的真正 threshold 值。
  当同一个索引位置的节点在增加后达到 9 个时，并且此时数组的长度大于等于 64，则会触发链表节点（Node）转红黑树节点（TreeNode），转成红黑树节点后，其实链表的结构还存在，通过 next 属性维持。链表节点转红黑树节点的具体方法为源码中的 treeifyBin 方法。而如果数组长度小于64，则不会触发链表转红黑树，而是会进行扩容。

• 当同一个索引位置的节点在移除后达到 6 个时，并且该索引位置的节点为红黑树节点，会触发红黑树节点转链表节点。红黑树节点转链表节点的具体方法为源码中的 untreeify 方法。

• HashMap 在 JDK 1.8 之后不再有死循环的问题，JDK 1.8 之前存在死循环的根本原因是在扩容后同一索引位置的节点顺序会反掉。

• HashMap 是非线程安全的，在并发场景下使用 ConcurrentHashMap 来代替。
  (12条消息) 面试阿里，HashMap 这一篇就够了_程序员囧辉-CSDN博客

经典连坏夺命Call

能否使用任何类作为 Map 的 key？

可以使用任何类作为 Map 的 key，然而在使用之前，需要考虑以下几点：

如果类重写了 equals() 方法，也应该重写 hashCode() 方法。

类的所有实例需要遵循与 equals() 和 hashCode() 相关的规则。

如果一个类没有使用 equals()，不应该在 hashCode() 中使用它。

用户自定义 Key 类最佳实践是使之为不可变的，这样 hashCode() 值可以被缓存起来，拥有更好的性能。不可变的类也可以确保 hashCode() 和 equals() 在未来不会改变，这样就会解决与可变相关的问题了。

为什么HashMap中String、Integer这样的包装类适合作为K？

答：String、Integer等包装类的特性能够保证Hash值的不可更改性和计算准确性，能够有效的减少Hash碰撞的几率

都是final类型，即不可变性，保证key的不可更改性，不会存在获取hash值不同的情况
内部已重写了equals()、hashCode()等方法，遵守了HashMap内部的规范（不清楚可以去上面看看putValue的过程），不容易出现Hash值计算错误的情况；

如果使用Object作为HashMap的Key，应该怎么办呢？

答：重写hashCode()和equals()方法

重写hashCode()是因为需要计算存储数据的存储位置，需要注意不要试图从散列码计算中排除掉一个对象的关键部分来提高性能，这样虽然能更快但可能会导致更多的Hash碰撞；
重写equals()方法，需要遵守自反性、对称性、传递性、一致性以及对于任何非null的引用值x，x.equals(null)必须返回false的这几个特性，目的是为了保证key在哈希表中的唯一性；
HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table的下标？
答：hashCode()方法返回的是int整数类型，其范围为-(2 ^ 31)~(2 ^ 31 – 1)，约有40亿个映射空间，而HashMap的容量范围是在16（初始化默认值）~2 ^ 30，HashMap通常情况下是取不到最大值的，并且设备上也难以提供这么多的存储空间，从而导致通过hashCode()计算出的哈希值可能不在数组大小范围内，进而无法匹配存储位置；

那怎么解决呢？

HashMap自己实现了自己的hash()方法，通过两次扰动使得它自己的哈希值高低位自行进行异或运算，降低哈希碰撞概率也使得数据分布更平均；
在保证数组长度为2的幂次方的时候，使用hash()运算之后的值与运算（&）（数组长度 – 1）来获取数组下标的方式进行存储，这样一来是比取余操作更加有效率，二来也是因为只有当数组长度为2的幂次方时，h&(length-1)才等价于h%length，三来解决了“哈希值与数组大小范围不匹配”的问题；

HashMap 的长度为什么是2的幂次方？

为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀，每个链表/红黑树长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。

这个算法应该如何设计呢？

我们首先可能会想到采用%取余的操作来实现。但是，重点来了：“取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作（也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）。” 并且 采用二进制位操作 &，相对于%能够提高运算效率，这就解释了 HashMap 的长度为什么是2的幂次方。

那为什么是两次扰动呢？

答：这样就是加大哈希值低位的随机性，使得分布更均匀，从而提高对应数组存储下标位置的随机性&均匀性，最终减少Hash冲突，两次就够了，已经达到了高位低位同时参与运算的目的；
(12条消息) Java集合容器面试题（2020最新版）_ThinkWon的博客-CSDN博客_集合面试题java

表亲**：ConcurrentHashMap（主流） 和 Hashtable (低能)**

1.Hashtable 全程加锁 不可以put null值

2.hashMap可以为 hash方法 可以设置key==null

fail-fast 和fial-safe：这是juc的两个机制：(12条消息) 快速失败(fail-fast)和安全失败(fail-safe)_zhanggf的博客-CSDN博客

树

树~ 数据结构里面的真正“豪门”，各个领域都是它们。

二叉搜索树

二叉搜索树是什么？（小左大右）

所谓二叉搜索树，可提供对数时间的元素插入和访问。二叉搜索树的节点放置规则是：任何节点的键值一定大于去其左子树中的每一个节点的键值，并小于其右子树的每一个节点的键值。

avl树

极致平衡！

平衡二叉搜索树(树的高度小，会左旋，会右旋)

(12条消息) 详细图文——AVL树_带翅膀的猫的博客-CSDN博客_avl树

红黑树（我也还没弄明白 wuwu~）

折中选择

1.他和avl树的区别：

查询多一次

插入和删除方便！

b -树

“矮胖树” 数据库索引用 mgonodb用过

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qXR5g2pY-1624420371762)(E:\工具包\Typora\Typora 图片\b树.png)]

b+树

跟b树的区别：

叶子节点负责数据： 其他节点只有索引：也就意味比原来更加“矮胖”。

b*树

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Xgrmtvxk-1624420371768)(E:\工具包\Typora\Typora 图片\b 星树.png)]

Lsm树

LSM树本质上就是在读写之间取得平衡，和B+树相比，它牺牲了部分读性能，用来大幅提高写性能。

[(12条消息) HBase] LSM树 VS B+树_Zhu_Julian’s Notes (朱显杰的技术博客）-CSDN博客_lsm树

题外话：comparable 和 comparator的区别？

comparable接口实际上是出自java.lang包，它有一个 compareTo(Object obj)方法用来排序
comparator接口实际上是出自 java.util 包，它有一个compare(Object obj1, Object obj2)方法用来排序

一般来说那些可是实现”排序”的集合类都更这两个有关联。

总结

头回写文章，格式逻辑什么都有可能不对。有的知识点还没整理上，还希望各位大佬多多指教。另外有什么好的学习方法也可评论告诉我哦~
我是悟空，越努力，越幸运~ 终有一天会变成超级赛亚人的！
再会，各位。

一键三连加关注，大厂offer挡不住😍~

今天的文章Java世界观：数据结构那些事儿，看完直接对线去分享到此就结束了，感谢您的阅读。