Java基础1-String/List/TreeSet/TreeMap

  • 时间:
  • 浏览:
  • 来源:互联网

Java基础1-String/List/TreeSet/TreeMap

文章目录

      • Java基础1-String/List/TreeSet/TreeMap
        • Stringbuffer和Stringbuilder的区别?
        • ArrayList和LinkedList以及vector区别?
        • 有关于TreeSet
        • 有关于TreeMap
        • 有关于红黑树

Stringbuffer和Stringbuilder的区别?

  • Stringbuffer是线程安全的(加了synchronized关键字),Stringbuilder是不安全的,方法基本一致
  • Stringbuffer中有个toStringCache字段,字段上的解释是返回最后一次toString的缓存值,一旦StringBuffer被修改就清除这个缓存值。如:
    • image-20210320163554956
    • 在这里会用到toStringCache,如果没改过(!=null),就不用复制了,于是会加快一些运行速度,但是呢,由于synchronized锁的存在,总体速度我认为还是Stringbuilder比较高。
    • image-20210320165035946

ArrayList和LinkedList以及vector区别?

  • 这个问题应该从三者的底层数据结构来看:

    • LinkedList底层是链表,因此考虑链表的优缺点即可——随机比较慢(get方法是有的),但是插入删除快

      • 从构造函数可以知道,这玩意是个双向链表,且有俩指针:first last
        • image-20210320180527519
      • get的实现:
        • 首先check保证index合法性,相当于越界检查,然后调用node方法,返回元素的item属性——相当于value
          • image-20210320181731096
        • 而从node方法中可以知道,get方法的实现平均时间复杂度为n/4,因为它将遍历分成两种模式,向前/向后,于是最长不超过长度的一半(size>>1是移位,相当于处以2,但是更快)
        • image-20210320180428816
    • ArrayList底层是数组,因此考虑数组的优缺点即可——随机查找快,但是插入删除(尤其是前部的)慢

      • 从源码可以知道,他的get是直接返回下标就行了
        • image-20210320181830050
      • 但是呢add方法就有意思了,从下面源码可以看到,它调用了系统的arraycopy,于是就慢了
        • image-20210320182158721
      • 还有一点就是ArrayList的iterator迭代器在多线程的状态下可能会发生数据混乱。
    • vector的底层也是数组,对比ArrayList可以发现是非常类似的,因此在大多数情况下我们可以吧ArrayList当成强化版的vector:

      • image-20210320195959415
      • image-20210320201017503
      • 但是呢,我们从下面的源码可以观察到(get方法),vector在get方法上都上了锁。。。。于是可想而知在多线程情况下的效率低下,但是他是线程安全的,而ArrayList则没有synchronized,也没见到其他保证线程安全的机制,于是可以认为它是不安全的。

        • //ArrayList
          public E get(int index) {
              rangeCheck(index);
          
              return elementData(index);
          }
          //vector
          public synchronized E get(int index) {
            if (index >= elementCount)
              throw new ArrayIndexOutOfBoundsException(index);
          
            return elementData(index);
           }
          
          
      • 再有呢,就是扩容规则上的区别,ArrayList每次扩容1.5倍(大约,因为移位的关系),而vector每次加一个capacityIncrement (这个值在初始化的时候可以设置的)

        • //ArrayList
          private void grow(int minCapacity) {
              // overflow-conscious code
              int oldCapacity = elementData.length;
              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);
          }
          
          //vector
          private void grow(int minCapacity) {
            //而且俺发现,这个minCapacity在自动扩容的时候是一个一个扩容的。。。。这个效率低得离谱
            // overflow-conscious code
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                             capacityIncrement : oldCapacity);
            if (newCapacity - minCapacity < 0)
              newCapacity = minCapacity;
            if (newCapacity - MAX_ARRAY_SIZE > 0)
              newCapacity = hugeCapacity(minCapacity);
            elementData = Arrays.copyOf(elementData, newCapacity);
          }
          
          
          //add算法扩容的时候参数是elementCount+1。。。。。就扩容了一个
          private void ensureCapacityHelper(int minCapacity) {
            // overflow-conscious code
            if (minCapacity - elementData.length > 0)
              grow(minCapacity);
          }
          
          
          public synchronized boolean add(E e) {
            modCount++;
            ensureCapacityHelper(elementCount + 1);
            elementData[elementCount++] = e;
            return true;
          }
          

有关于TreeSet

  • 他是基于NavigableMap实现,而在构造中传的是TreeMap,代码摘出如下:

  • private transient NavigableMap<E,Object> m;
    TreeSet(NavigableMap<E,Object> m) {
      this.m = m;
    }
    public TreeSet() {
      this(new TreeMap<E,Object>());
    }
    
  • 我们翻一翻TreeMap的源码,可以看到TreeMap是implement了NavigableMap

    • image-20210321000027719
  • 于是我们看TreeSet的源码可以发现,基本都是调用NavigableMap(或者可以说TreeMap)的方法,只不过它用不到TreeMap的value(直接用的PRESENT填充了),随便找一点:

    • image-20210321000850846
  • 然后看看TreeMap的实现

有关于TreeMap

 private transient Entry<K,V> root;
 // Red-black mechanics
 private static final boolean RED   = false;
 private static final boolean BLACK = true;
 //这是基于红黑树的实现的entry,可以预见一定还有一个改变color的方法
 static final class Entry<K,V> implements Map.Entry<K,V> {
   K key;
   V value;
   Entry<K,V> left;
   Entry<K,V> right;
   Entry<K,V> parent;
   boolean color = BLACK;
   /**
          * Make a new cell with given key, value, and parent, and with
          * {@code null} child links, and BLACK color.
          */
   Entry(K key, V value, Entry<K,V> parent) {
     this.key = key;
     this.value = value;
     this.parent = parent;
   } 
   //其他还有些getset以及equal和tostring就省略了
 }
  • get方法

  • public V get(Object key) {
      //只是调用getEntry,然后做了一个判空
      Entry<K,V> p = getEntry(key);
      return (p==null ? null : p.value);
    }
    	//getEntry就是走红黑树
    final Entry<K,V> getEntry(Object key) {
      // Offload comparator-based version for sake of performance
      if (comparator != null)
        return getEntryUsingComparator(key);
      if (key == null)
        throw new NullPointerException();
      @SuppressWarnings("unchecked")
      Comparable<? super K> k = (Comparable<? super K>) key;
      Entry<K,V> p = root;
      while (p != null) {
        int cmp = k.compareTo(p.key);
        if (cmp < 0)
          p = p.left;
        else if (cmp > 0)
          p = p.right;
        else
          return p;
      }
      return null;
    }
    
  • Put方法

  • public V put(K key, V value) {
      Entry<K,V> t = root;
    	//若树为空,则点作为root节点
      if (t == null) {
        compare(key, key); // type (and possibly null) check
    
        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
      }
      int cmp;
      Entry<K,V> parent;
      // split comparator and comparable paths
     	// 比较器
      Comparator<? super K> cpr = comparator;
      // 走树,找到空节点的parent
      if (cpr != null) {
        do {
          parent = t;
          cmp = cpr.compare(key, t.key);
          if (cmp < 0)
            t = t.left;
          else if (cmp > 0)
            t = t.right;
          else
            return t.setValue(value);
        } while (t != null);
      }
      else {
        if (key == null)
          throw new NullPointerException();
        @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
        do {
          parent = t;
          cmp = k.compareTo(t.key);
          if (cmp < 0)
            t = t.left;
          else if (cmp > 0)
            t = t.right;
          else
            return t.setValue(value);
        } while (t != null);
      }
      //插入节点
      Entry<K,V> e = new Entry<>(key, value, parent);
      if (cmp < 0)
        parent.left = e;
      else
        parent.right = e; 
      fixAfterInsertion(e);
      size++;
      modCount++;
      return null;
    }
    //调整插入后的红黑树
    private void fixAfterInsertion(Entry<K,V> x) {
      x.color = RED;
    
      while (x != null && x != root && x.parent.color == RED) {
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
          Entry<K,V> y = rightOf(parentOf(parentOf(x)));
          if (colorOf(y) == RED) {
            setColor(parentOf(x), BLACK);
            setColor(y, BLACK);
            setColor(parentOf(parentOf(x)), RED);
            x = parentOf(parentOf(x));
          } else {
            if (x == rightOf(parentOf(x))) {
              x = parentOf(x);
              rotateLeft(x);
            }
            setColor(parentOf(x), BLACK);
            setColor(parentOf(parentOf(x)), RED);
            rotateRight(parentOf(parentOf(x)));
          }
        } else {
          Entry<K,V> y = leftOf(parentOf(parentOf(x)));
          if (colorOf(y) == RED) {
            setColor(parentOf(x), BLACK);
            setColor(y, BLACK);
            setColor(parentOf(parentOf(x)), RED);
            x = parentOf(parentOf(x));
          } else {
            if (x == leftOf(parentOf(x))) {
              x = parentOf(x);
              rotateRight(x);
            }
            setColor(parentOf(x), BLACK);
            setColor(parentOf(parentOf(x)), RED);
            rotateLeft(parentOf(parentOf(x)));
          }
        }
      }
      root.color = BLACK;
    }
    

有关于红黑树

image-20210321002726730
  • 要求:
    • 根节点是黑色的
    • 叶节点为不存储数据的黑色空节点
    • 任何相邻的两个节点不能同时为红色
    • 任意节点到其可到达的叶节点间包含相同数量的黑色节点
  • 非严格的平衡二叉树,于是每次插入的时候有时候并不需要复杂的旋转平衡操作,代价是查找效率微微降低(数量级不变)

本文链接http://www.dzjqx.cn/news/show-617175.html