java 基础数据结构

[toc]

为啥

昨天看了一下hashMap的源码,感觉里面的东西真的很不错,尤其是一些巧妙的实现,和代码规范.真的服气他们的设计思路. 大概两年以后才能追上

LinkedHashMap

继承自hashmap 但是重写了其方法,

与hashmap不同的是,由于hashmap是计算hash然后放入对应位置.不保证进入顺序和出来的顺序
LinkedHashMap是可以保证输出顺序是完成按照插入顺序

Entry

集成了hashmap的Entry,但是增加了before和after的引用.

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

一共三个一个保存值,另外是引用

put

put方法没有重新很多,就是添加节点的时候重新了,保证顺序嘛

    //重写了hashmap添加节点,把before和after指向了
  void createEntry(int hash, K key, V value, int bucketIndex) {
    HashMap.Entry<K,V> old = table[bucketIndex];
    Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
    table[bucketIndex] = e;
    // 调用元素的addBrefore方法，将元素加入到哈希、双向链接列表.
    e.addBefore(header);
    size++;
  }

get

的

ArrayList

构造函数

• public ArrayList()可以构造一个默认初始容量为10的空列表；
• public ArrayList(int initialCapacity)构造一个指定初始容量的空列表；
• public ArrayList(Collection<? extends E> c)构造一个包含指定 collection 的元素的列表，这些元素按照该collection的迭代器返回它们的顺序排列的

set get

• set

  // 先调用index越界检测
  rangeCheck(index);
  E oldValue = elementData(index);
  // 把值替换就行了
  elementData[index] = element;
  return oldValue;
  

• add:添加默认添加在末尾, 可以index添加在索引之后
• get(index): 先判断越界,然后返回rangeCheck(index);return (E) elementData[index];
• 删除: remove: 可以删除index,System.arraycopy(elementData, index+1, elementData, index,numMoved); elementData[--size] = null;
  也可以删除对象Object

  public boolean remove(Object o) {
  if (o == null) {
      for (int index = 0; index < size; index++)
          if (elementData[index] == null) {
              fastRemove(index);
              return true;
          }
  } else {
      for (int index = 0; index < size; index++)
          if (o.equals(elementData[index])) {
              fastRemove(index);
              return true;
          }
  }
  return false;
  }
  

• grow:扩容当添加元素时要检测元素然后进行扩容

  private void grow(int minCapacity) {
  // overflow-conscious code
  int oldCapacity = elementData.length;
  //扩了1.5倍
  int newCapacity = oldCapacity + (oldCapacity >> 1);
  if (newCapacity - minCapacity < 0)
      newCapacity = minCapacity;
  if (newCapacity - MAX_ARRAY_SIZE > 0)
      newCapacity = hugeCapacity(minCapacity);
  // minCapacity is usually close to size, so this is a win:
  //复制函数
  elementData = Arrays.copyOf(elementData, newCapacity);
  }
  

LinkedList

其实这个就没有什么了;就是链表喽
node的基础类: 有next 和prev两个引用

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

双向链表 类中有两个指向 first 和 last; 平时的插入和删除都是通过这两个进行遍历的

/**
 * Pointer to first node.
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node<E> first;
/**
 * Pointer to last node.
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node<E> last;

• add(E e)
  其实直接调用linkLast() 插入到最后即可

  final Node<E> l = last;
  final Node<E> newNode = new Node<>(l, e, null);
  last = newNode;
  

• add(int index,E e); 插入至指定index 使用linkBefore();
  

  就是链表之间的增删改查而已