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

冷不防 2022-11-11 14:46 252阅读 0赞

### 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][]

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

[image-20210320163554956]: /images/20221022/82dbc01016e1424db0fb4d1d021aa173.png
[image-20210320165035946]: http://docker.aliyouth.cn/img/image-20210320165035946.png
[image-20210320180527519]: http://docker.aliyouth.cn/img/image-20210320180527519.png
[image-20210320181731096]: http://docker.aliyouth.cn/img/image-20210320181731096.png
[image-20210320180428816]: http://docker.aliyouth.cn/img/image-20210320180428816.png
[image-20210320181830050]: http://docker.aliyouth.cn/img/image-20210320181830050.png
[image-20210320182158721]: http://docker.aliyouth.cn/img/image-20210320182158721.png
[image-20210320195959415]: http://docker.aliyouth.cn/img/image-20210320195959415.png
[image-20210320201017503]: http://docker.aliyouth.cn/img/image-20210320201017503.png
[image-20210321000027719]: http://docker.aliyouth.cn/img/image-20210321000027719.png
[image-20210321000850846]: http://docker.aliyouth.cn/img/image-20210321000850846.png
[image-20210321002726730]: http://docker.aliyouth.cn/img/image-20210321002726730.png