数据结构

介绍💒

• 待写

HashMap✋

• 数据结构: Array LinkedList Tree

• 实现

  • 默认构造方法不会创建内部的数组对象
  • put方法调用过程,判断内部是否创建了数组对象，没有创建则创建。
    • 计算key的hashCode如果在数组中不存在则存入进去
      • 判断两个对象hash值和对象地址对比是否一样 不一样继续判断 equals 对比也不一样 (hash值一样，地址不一样,equals也不一样则往下走)
      • 判断有没有变成树
      • 变成链表放入其中：如果，链表大于8并且HashMap的数组大于64则转换成树
    • size++
    • 执行完毕
  • 默认长度为: 16 负载因子: 0.75

• putVal方法

• 省略其他方法

public class HashMap{
  final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                 boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0) //判断数组是否为空，为空则创建
      n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null) //判断计算hash是否在数组存在，不存在则插入
      tab[i] = newNode(hash, key, value, null);
    else { //hash冲突处理
      Node<K,V> e; K k;
      if (p.hash == hash &&
              ((k = p.key) == key || (key != null && key.equals(k)))) 
        e = p;
      else if (p instanceof TreeNode)
        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
      else {
        for (int binCount = 0; ; ++binCount) {
          if ((e = p.next) == null) {
            p.next = newNode(hash, key, value, null);
            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
              treeifyBin(tab, hash);
            break;
          }
          if (e.hash == hash &&
                  ((k = e.key) == key || (key != null && key.equals(k))))
            break;
          p = e;
        }
      }
      if (e != null) { // existing mapping for key
        V oldValue = e.value;
        if (!onlyIfAbsent || oldValue == null)
          e.value = value;
        afterNodeAccess(e);
        return oldValue;
      }
    }
    ++modCount;
    if (++size > threshold)
      resize();
    afterNodeInsertion(evict);
    return null;
  }
}

LinkedList🍅

• 数据结构: 链表
• 特点: 内存不连续，在一个对象中存储下一个对象a > b > c > d
• 优点: 插入，删除快。因为只需要把引用重新指定一下即可。
• 缺点: 查询慢，需要遍历元素，元素越多遍历的时间越久

Array🐯

• 数据结构: 数组
• 特点: 内存连续，查询快。用于HashMap ArrayList的底层实现

Stack👏

• 数据结构: 栈
• 特点: 后进先出，可以使用数组和链表进行实现，目前数组优先效果更好
• 理解: 叠加凳子，后放的凳子会在最前面，这就是现实中的对比

Queue👏

• 数据结构: 队列
• 特点: 先进先出，可以使用数组和链表进行实现，目前链表优先效果更好