Home IT Linux Windows Database Network Programming Server Mobile  
           
  Home \ Programming \ Java collections series     - Linux installed and tested the deployment of Kafka distributed cluster (Server)

- Port Telnet command to detect the remote host is turned on (Linux)

- Linux security configuration (Linux)

- Linux 10 useful examples of command-line completion (Linux)

- TOAST function in PostgreSQL (Database)

- Learning and Practice (Linux)

- Linux Getting Started tutorial: XWindow what (Linux)

- Storm how to ensure that at least once semantics (Programming)

- NaSC using simple mathematical operations on Ubuntu and Elementary OS (Linux)

- To install minimize RHEL / CentOS 7 (Linux)

- Java in several ways of using MongoDB (Programming)

- FPM quickly create packages with RPM (Linux)

- C language binary tree counts words (Programming)

- Verify the character set on MyCAT (Database)

- Setting grep Highlight Matches (Linux)

- Linux Routine Task Scheduler (Linux)

- CentOS 7 How to connect to a wireless network (Linux)

- Java by Spy Memcached to cache data (Programming)

- vector C ++ sequence containers (Programming)

- Use regular expressions to check whether the input box to enter a URL (Programming)

 
         
  Java collections series
     
  Add Date : 2017-01-08      
         
       
         
  Read catalog

One, ArrayList Profile
Two, ArrayList source code analysis
Three, ArrayList traversal


One, ArrayList Profile

ArrayList index sequence is dynamically grow and shrink, which is based on an array implementations List class.

This class encapsulates a dynamic reallocation of Object [] array, each object has a capacity class attribute, indicating that they are packaged Object [] length of the array, when adding elements to the ArrayList, and the property value will automatically increase . If you want to add a lot of elements in the ArrayList, use the method ensureCapacity time increase capacity, can be reduced to increase the number of re-allocation to improve performance.

And Vector to ArrayList usage is similar, but Vector is an older set, a number of disadvantages, not recommended. In addition, the difference between the ArrayList and Vector are: ArrayList is thread safe, when multiple threads access the same set of a ArrayList, the program will need to manually ensure the synchronization of the collection, while Vector is thread safe.

Two, ArrayList source code analysis

Here ArrayList source code for a simple analysis:

public class ArrayList < E> extends AbstractList < E> implements List < E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;
    // Default initial capacity of 10
    private static final int DEFAULT_CAPACITY = 10;
    private static final Object [] EMPTY_ELEMENTDATA = {};
    private static final Object [] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    transient Object [] elementData;
    Number // ArrayList actual data
    private int size;
    public ArrayList (int initialCapacity) // constructor with the size of the initial capacity
    {
        if (initialCapacity> 0) // initial capacity is greater than 0, instantiate an array
        {
            this.elementData = new Object [initialCapacity];
        }
        else if (initialCapacity == 0) // initialize equal to 0, an empty array to elementData
        {
            this.elementData = EMPTY_ELEMENTDATA;
        }
        else // initial capacity is less than, Throws
        {
            throw new IllegalArgumentException ( "Illegal Capacity:" + initialCapacity);
        }
    }
    public ArrayList () // no-argument constructor, the default capacity of 10
    {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    public ArrayList (Collection < ? extends E> c) // Create a collection of ArrayList
    {
        elementData = c.toArray (); // Returns an array containing all of the elements c
        if ((size = elementData.length)! = 0)
        {
            if (elementData.getClass ()! = Object []. class)
                elementData = Arrays.copyOf (elementData, size, Object [] class.); // Copies the specified array, so that a specified length elementData
        }
        else
        {
            // C is not element
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
    // Set to the current value of the current capacity of the actual size of the elements
    public void trimToSize ()
    {
        modCount ++;
        if (size < elementData.length)
        {
            elementData = (size == 0) EMPTY_ELEMENTDATA: Arrays.copyOf (elementData, size);?
        }
    }
    
    // Set the capacit increase minCapacity
    public void ensureCapacity (int minCapacity)
    {
        int minExpand = (elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA!) 0: DEFAULT_CAPACITY;?
        if (minCapacity> minExpand)
        {
            ensureExplicitCapacity (minCapacity);
        }
    }
    private void ensureCapacityInternal (int minCapacity)
    {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
        {
            minCapacity = Math.max (DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity (minCapacity);
    }
    private void ensureExplicitCapacity (int minCapacity)
    {
        modCount ++;
        if (minCapacity - elementData.length> 0)
            grow (minCapacity);
    }
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    private void grow (int minCapacity)
    {
        int oldCapacity = elementData.length;
// Note expand capacity here is the way it is right one plus the original number, in fact, expanded by 1.5 times
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE> 0)
            newCapacity = hugeCapacity (minCapacity);
        elementData = Arrays.copyOf (elementData, newCapacity);
    }
    private static int hugeCapacity (int minCapacity)
    {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError ();
        return (minCapacity> MAX_ARRAY_SIZE)?
            Integer.MAX_VALUE:
            MAX_ARRAY_SIZE;
    }
    // Returns the size of the ArrayList
    public int size ()
    {
        return size;
    }
    // Determine ArrayList is empty
    public boolean isEmpty () {
        return size == 0;
    }
    // Determine whether an ArrayList contains Object (o)
    public boolean contains (Object o) {
        return indexOf (o)> = 0;
    }
    // Forward lookup, returns the ArrayList elements Object (o) index position
    public int indexOf (Object o)
    {
        if (o == null) {
            for (int i = 0; i < size; i ++)
                if (elementData [i] == null)
                    return i;
        }
        else
        {
            for (int i = 0; i < size; i ++)
                if (o.equals (elementData [i]))
                    return i;
        }
        return -1;
    }
    // Reverse lookup, Return ArrayList elements Object (o) index position
    public int lastIndexOf (Object o) {
        if (o == null) {
            for (int i = size-1; i> = 0; i--)
                if (elementData [i] == null)
                    return i;
        } Else {
            for (int i = size-1; i> = 0; i--)
                if (o.equals (elementData [i]))
                    return i;
        }
        return -1;
    }
    // Returns a shallow copy of this ArrayList instance.
    public Object clone ()
    {
        try
        {
            < ?> ArrayList v = (ArrayList < ?>) Super.clone ();
            v.elementData = Arrays.copyOf (elementData, size);
            v.modCount = 0;
            return v;
        }
        catch (CloneNotSupportedException e) {
            // This should not happen, since we are Cloneable
            throw new InternalError (e);
        }
    }
    // Returns an array containing all of the elements of an ArrayList
    public Object [] toArray () {
        return Arrays.copyOf (elementData, size);
    }
    @SuppressWarnings ( "Unchecked")
    public < T> T [] toArray (T [] a) {
        if (a.length < size)
            return (T []) Arrays.copyOf (elementData, size, a.getClass ());
        System.arraycopy (elementData, 0, a, 0, size);
        if (a.length> size)
            a [size] = null;
        return a;
    }
    @SuppressWarnings ( "Unchecked")
    E elementData (int index) {
        return (E) elementData [index];
    }
    
    // Returns to the specified index value
    public E get (int index)
    {
        rangeCheck (index); // Check if the given index value is out of range
        return elementData (index);
    }
   
    // The value specified index is replaced with a new value and return the old value
    public E set (int index, E element)
    {
        rangeCheck (index);
        E oldValue = elementData (index);
        elementData [index] = element;
        return oldValue;
    }
    
    // The specified element to the tail of this list
    public boolean add (E e)
    {
        ensureCapacityInternal (size + 1);
        elementData [size ++] = e;
        return true;
    }
    
    // Add the element to the specified location of the ArrayList
    public void add (int index, E element) {
        rangeCheckForAdd (index);
        ensureCapacityInternal (size + 1);
       
        // Copy from the specified source array in an array, beginning at the specified location, until the end of the destination array specified location.
        // Arraycopy (copied array, starting from the first copy several elements to be copied to the array element from the first few start pasting, a total number of elements need to be copied)
        // That array elementData starting index position, copied to index + 1 position, total copy size-index elements
        System.arraycopy (elementData, index, elementData, index + 1, size - index);
        elementData [index] = element;
        size ++;
    }
    
    // Remove the element ArrayList specified position
    public E remove (int index)
    {
        rangeCheck (index);
        modCount ++;
        E oldValue = elementData (index);
        int numMoved = size - index - 1;
        if (numMoved> 0)
            System.arraycopy (elementData, index + 1, elementData, index, numMoved);
        elementData [- size] = null; // array of original final position is set to null
        return oldValue;
    }
    
    // Remove the first occurrence of the specified element ArrayList (if present).
    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;
    }
    
    // Quickly delete the element at the specified position
    private void fastRemove (int index)
    {
        modCount ++;
        int numMoved = size - index - 1;
        if (numMoved> 0)
            System.arraycopy (elementData, index + 1, elementData, index, numMoved);
        elementData [- size] = null;
    }
   
    // Empty ArrayList, all elements set to null
    public void clear ()
    {
        modCount ++;
        for (int i = 0; i < size; i ++)
            elementData [i] = null;
        size = 0;
    }
    
    // C in accordance with the order of elements returned by iterator, add c all elements in the tail of this list
    public boolean addAll (Collection < ? extends E> c) {
        Object [] a = c.toArray ();
        int numNew = a.length;
        ensureCapacityInternal (size + numNew); // Increments modCount
        System.arraycopy (a, 0, elementData, size, numNew);
        size + = numNew;
        ! Return numNew = 0;
    }
    
    // Starting at the specified location index, c all the specified element into this list
    public boolean addAll (int index, Collection < ? extends E> c) {
        rangeCheckForAdd (index);
        Object [] a = c.toArray ();
        int numNew = a.length;
        ensureCapacityInternal (size + numNew); // Increments modCount
        int numMoved = size - index;
        if (numMoved> 0)
            // First element from the ArrayList numMoved index started to move back to the starting position for the index + numNew go
            System.arraycopy (elementData, index, elementData, index + numNew, numMoved);
        // C and then copy the numNew elements to the starting position for the index storage to go
        System.arraycopy (a, 0, elementData, index, numNew);
        size + = numNew;
        ! Return numNew = 0;
    }
    
    // Remove all elements to fromIndex between toIndex
    protected void removeRange (int fromIndex, int toIndex)
    {
        modCount ++;
        // NumMoved the number of elements to delete the index back
        int numMoved = size - toIndex;
        // Delete the index will be copied to the elements behind the starting position to fromIndex storage space to go
        System.arraycopy (elementData, toIndex, elementData, fromIndex, numMoved);
        int newSize = size - (toIndex-fromIndex);
        // The ArrayList later (toIndex-fromIndex) elements is set to null
        for (int i = newSize; i < size; i ++)
        {
            elementData [i] = null;
        }
        size = newSize;
    }
    
    // Check whether the index is out of bounds
    private void rangeCheck (int index)
    {
        if (index> = size)
            throw new IndexOutOfBoundsException (outOfBoundsMsg (index));
    }
    private void rangeCheckForAdd (int index)
    {
        if (index> size || index < 0)
            throw new IndexOutOfBoundsException (outOfBoundsMsg (index));
    }
    
    private String outOfBoundsMsg (int index) {
        return "Index:" + index + ", Size:" + size;
    }
    
    // Remove element ArrayList contained in the c
    public boolean removeAll (Collection < ?> c)
    {
        Objects.requireNonNull (c);
        return batchRemove (c, false);
    }
    
    // Delete ArrayList, in addition to the elements contained in the c, and contrary removeAll
    public boolean retainAll (Collection < ?> c)
    {
        Objects.requireNonNull (c); // Checks if the specified object is empty
        return batchRemove (c, true);
    }
    
    private boolean batchRemove (Collection < ?> c, boolean complement) {
        final Object [] elementData = this.elementData;
        int r = 0, w = 0;
        boolean modified = false;
        try
        {
            for (; r < size; r ++)
                if (c.contains (elementData [r]) == complement) // c is determined whether there elementData [r] element

                    elementData [w ++] = elementData [r];
        }
        finally
        {
            if (r! = size)
            {
                System.arraycopy (elementData, r, elementData, w, size - r);
                w + = size - r;
            }
            if (w! = size)
            {
                // Clear to let GC do its work
                for (int i = w; i < size; i ++)
                    elementData [i] = null;
                modCount + = size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }
    
    // ArrayList of the "capacity of all the elements of value" are written to the output stream
    private void writeObject (java.io.ObjectOutputStream s) throws java.io.IOException
    {
        int expectedModCount = modCount;
        s.defaultWriteObject ();
        // Write array size
        s.writeInt (size);
        // Write all elements of the array
        for (int i = 0; i < size; i ++) {
            s.writeObject (elementData [i]);
        }
        if (modCount! = expectedModCount) {
            throw new ConcurrentModificationException ();
        }
    }
    
    // First ArrayList "size" is read out, and then "all the elements of value" is read out
    private void readObject (java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        elementData = EMPTY_ELEMENTDATA;
        s.defaultReadObject ();
        s.readInt (); // ignored
        if (size> 0) {
            // Be like clone (), allocate array based upon size not capacity
            ensureCapacityInternal (size);
            Object [] a = elementData;
            // Read in all elements in the proper order.
            for (int i = 0; i < size; i ++) {
                a [i] = s.readObject ();
            }
        }
    }
Three, ArrayList traversal

ArrayList supports three kinds of traversal

1, through the iterator traversal:

    Iterator iter = list.iterator ();
    while (iter.hasNext ())
    {
        System.out.println (iter.next ());
    }
2, a random access by index value to traverse, since ArrayList implements the interface RandomAccess

    int size = list.size ();
    for (int i = 0; i < size; i ++)
    {
        System.out.println (list.get (i));
    }
3, for loop iterates:

    for (String str: list)
    {
    System.out.println (str);
}
The complete code examples are as follows:

public class DemoMain
{
    public static void main (String [] args)
    {
        List < String> list = new ArrayList < String> ();
        list.add ( "nihao");
        list.add ( "xujian");
        list.add ( "wang");
        System.out.println ( "-------- --------- through iterator traversal");
        Iterator iter = list.iterator ();
        while (iter.hasNext ())
        {
           System.out.println (iter.next ());
        }
        
        System.out.println ( "-------- --------- random access");
        int size = list.size ();
        for (int i = 0; i < size; i ++)
        {
            System.out.println (list.get (i));
        }
        
        System.out.println ( "-------- --------- iterate through for");
        for (String str: list)
        {
            System.out.println (str);
        }
    }
}

Read catalog

One, LinkedList Profile
Two, LinkedList source code analysis
Third, the Instructions About LinkedList
One, LinkedList Profile

LinkedList is a way to be efficient insertion and removal operations of the ordered sequence in any position, which is based on a doubly linked list implementation.

ps: There is a problem, is a data structure on the realization of LinkedList whether the doubly linked list cycles, search the Internet there are many articles say is cyclic, and some articles but I have read the source code that should not be circulated?

For example, in the tail of the list to delete the node code:

  private E unlinkLast (Node < E> l)
  {
        final E element = l.item;
        final Node < E> prev = l.prev;
        l.item = null;
        l.prev = null; // help GC
        last = prev;
        if (prev == null)
            first = null;
        else
            prev.next = null;
        size--;
        modCount ++;
        return element;
    }
After here to remove the tail node l, l will be the next previous node prev set to null, but does not refer to head node. I do not know the reason because the code version (my source code file is downloaded jdk1.8.0_45 acquired), to see if the reader know the reasons, hoping to help answer!

In the source code defines the basic structure of the node:

 private static class Node < E> {
        E item; // value of the node that contains the representation
        Node < E> next; // Expression of a current node
        Node < E> prev; // represents a current node

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


LinkedList is inherited from AbstractSequentialList a doubly linked list. It can also be used as a stack, queue, or double-ended queue operation.
LinkedList implement the List interface, it can perform queue operations.
LinkedList implement Deque interface, the LinkedList can use as a double-ended queue.
LinkedList implements the Cloneable interface, the covering function clone (), can be cloned.
LinkedList implements java.io.Serializable interface, which means LinkedList support serialization, go through the sequence of transmission.
LinkedList is asynchronous.

Two, LinkedList source code analysis

  1 public class LinkedList < E> extends AbstractSequentialList < E> implements List < E>, Deque < E>, Cloneable, java.io.Serializable
  2 {
  3 // implement Serilizable interface will not need to serialize the properties before you add the keyword transient, serialized object, this property will not be serialized to the specified destination.
  4 transient int size = 0;
  5 // points to the first node
  6 transient Node < E> first;
  7 // points to the last node
  8 transient Node < E> last;
  9 // construct an empty list
 10 public LinkedList () {
 11}
 12 // build a collection that contains a list of c
 13 public LinkedList (Collection < ? Extends E> c) {
 14 this ();
 15 addAll (c);
 16}
 17 // The value of e node node as the first node
 18 private void linkFirst (E e) {
 19 final Node < E> f = first;
 20 // Construction of a prev is null, next to f, e node is a node
 21 final Node < E> newNode = new Node < > (null, e, f);
 22 // The newNode as the first node
 23 first = newNode;
 24 // If there is no back newNode node as the last node will newNode
 25 if (f == null)
 26 last = newNode;
 27 // otherwise it will assign its newNode prev
 28 else
 29 f.prev = newNode;
 30 // length of the list plus one
 31 size ++;
 32 modCount ++;
 33}
 34 // The value of e node node as the last node
 35 void linkLast (E e) {
 36 final Node < E> l = last;
 37 // Construction of a prev value of l, next value of e is null, node
 38 final Node < E> newNode = new Node < > (l, e, null);
 39 last = newNode;
 40 if (l == null)
 41 first = newNode;
 42 else
 43 l.next = newNode;
 44 size ++;
 45 modCount ++;
 46}
 47 // non-empty before the insertion node node succ e
 48 void linkBefore (E e, Node < E> succ) {
 49 final Node < E> pred = succ.prev;
 50 // in front of the node and the succ succ as prev and next
 51 final Node < E> newNode = new Node < > (pred, e, succ);
 52 // then newNode as the succ prev
 53 succ.prev = newNode;
 54 // If the original succ is the first node, the node will be set as the default newNode
 55 if (pred == null)
 56 first = newNode;
 57 else
 58 pred.next = newNode;
 59 size ++;
 60 modCount ++;
 61}
 62 // release the first non-empty node f
 63 private E unlinkFirst (Node < E> f) {
 64 final E element = f.item;
 65 final Node < E> next = f.next;
 66 f.item = null;
 67 f.next = null; // help GC
 68 // The first node following node to the first node
 69 first = next;
 70 if (next == null)
 71 last = null;
 72 else
 73 next.prev = null;
 74 size--;
 75 modCount ++;
 76 return element;
 77}
 78 // release of non-empty end node l
 79 private E unlinkLast (Node < E> l) {
 80 final E element = l.item;
 81 final Node < E> prev = l.prev;
 82 l.item = null;
 83 l.prev = null; // help GC
 84 last = prev;
 85 if (prev == null)
 86 first = null;
 87 else
 88 prev.next = null;
 89 size--;
 90 modCount ++;
 91 return element;
 92}
 93 // delete a non-empty node x
 94 E unlink (Node < E> x)
 95 {
 96 final E element = x.item;
 97 final Node < E> next = x.next; // x rear node
 98 final Node < E> prev = x.prev; // x previous node
 99
100 if (prev == null) {
101 first = next;
102} else {
103 prev.next = next;
104 x.prev = null;
105}
106 if (next == null) {
107 last = prev;
108} else {
109 next.prev = prev;
110 x.next = null;
111}
112 x.item = null;
113 size--;
114 modCount ++;
115 return element;
116}
117 // returns a list of the first node element value
118 public E getFirst () {
119 final Node < E> f = first;
120 if (f == null)
121 throw new NoSuchElementException ();
122 return f.item;
123}
124 // node back end of the list element value
125 public E getLast () {
126 final Node < E> l = last;
127 if (l == null)
128 throw new NoSuchElementException ();
129 return l.item;
130}
131 // Remove the first node
132 public E removeFirst () {
133 final Node < E> f = first;
134 if (f == null)
135 throw new NoSuchElementException ();
136 return unlinkFirst (f);
137}
138 // remove the tail node
139 public E removeLast () {
140 final Node < E> l = last;
141 if (l == null)
142 throw new NoSuchElementException ();
143 return unlinkLast (l);
144}
145 // insert node e in the list header
146 public void addFirst (E e) {
147 linkFirst (e);
148}
149 // insert node e in the end of the list
150 public void addLast (E e) {
151 linkLast (e);
152}
153 // determine whether the list contains the elements o
154 public boolean contains (Object o) {
! 155 return indexOf (o) = -1;
156}
157 // returns a list of length size
158 public int size () {
159 return size;
160}
161 // insert an element in the end of the list
162 public boolean add (E e) {
163 linkLast (e);
164 return true;
165}
166 // remove node elements o
167 public boolean remove (Object o)
168 {
169 if (o == null) {
170 for (Node < E> x = first; x = null;! X = x.next) {
171 if (x.item == null) {
172 unlink (x);
173 return true;
174}
175}
176} else {
177 for (Node < E> x = first; x = null;! X = x.next) {
178 if (o.equals (x.item)) {
179 unlink (x);
180 return true;
181}
182}
183}
184 return false;
185}
186 // Add a collection c all elements to the end of the list
187 public boolean addAll (Collection < ? Extends E> c) {
188 return addAll (size, c);
189}
190 // start from the specified index position, the set of elements c inserted into the list
191 public boolean addAll (int index, Collection < ? Extends E> c) {
192 // First determine the legality of the insertion position
193 checkPositionIndex (index);
194 Object [] a = c.toArray ();
195 int numNew = a.length;
196 if (numNew == 0)
197 return false;
198 Node < E> pred, succ;
199 if (index == size) {// set of instructions inserted in the end of the list elements
200 succ = null;
201 pred = last;
202}
203 else {// Otherwise, find the node where the index
204 succ = node (index);
205 pred = succ.prev;
206}
207 for (Object o: a) {
208 @SuppressWarnings ( "unchecked") E e = (E) o;
209 Node < E> newNode = new Node < > (pred, e, null);
210 if (pred == null)
211 first = newNode;
212 else
213 pred.next = newNode;
214 pred = newNode;
215}
216 if (succ == null) {
217 last = pred;
218} else {
219 pred.next = succ;
220 succ.prev = pred;
221}
222 size + = numNew;
223 modCount ++;
224 return true;
225}
226 // delete the list of all nodes
227 public void clear () {
228 for (Node < E> x = first; x = null;!)
229 {
230 Node < E> next = x.next;
231 x.item = null;
232 x.next = null;
233 x.prev = null;
234 x = next;
235}
236 first = last = null;
237 size = 0;
238 modCount ++;
239}
240 // Get the specified index node element values
241 public E get (int index) {
242 checkElementIndex (index);
243 return node (index) .item;
244}
245 // replace the specified index node element values
246 public E set (int index, E element) {
247 checkElementIndex (index);
248 Node < E> x = node (index);
249 E oldVal = x.item;
250 x.item = element;
251 return oldVal;
252}
253 // insert element e before the specified index
254 public void add (int index, E element) {
255 checkPositionIndex (index);
256 if (index == size)
257 linkLast (element);
258 else
259 linkBefore (element, node (index));
260}
261 // remove the element at the specified position
262 public E remove (int index) {
263 checkElementIndex (index);
264 return unlink (node (index));
265}
266 // determine the specified index element exists
267 private boolean isElementIndex (int index) {
268 return index> = 0 && index < size;
269}
270 private boolean isPositionIndex (int index) {
271 return index> = 0 && index < = size;
272}
IndexOutOfBoundsException details 273 // Construction
274 private String outOfBoundsMsg (int index) {
275 return "Index:" + index + ", Size:" + size;
276}
277 private void checkElementIndex (int index) {
278 if (! IsElementIndex (index))
279 throw new IndexOutOfBoundsException (outOfBoundsMsg (index));
280}
281 private void checkPositionIndex (int index) {
282 if (! IsPositionIndex (index))
283 throw new IndexOutOfBoundsException (outOfBoundsMsg (index));
284}
285 // Returns the specified index node
286 Node < E> node (int index) {
287 // Here is a little trick, when the index < size / 2, starting from the first half of the list, otherwise start from the second half of
288 if (index < (size >> 1)) {
289 Node < E> x = first;
290 for (int i = 0; i < index; i ++)
291 x = x.next;
292 return x;
293} else {
294 Node < E> x = last;
295 for (int i = size - 1; i> index; i--)
296 x = x.prev;
297 return x;
298}
299} // returns the list o position the first time, if it exists, or -1
300 public int indexOf (Object o) {
301 int index = 0;
302 if (o == null) {
303 for (Node < E> x = first; x = null;! X = x.next) {
304 if (x.item == null)
305 return index;
306 index ++;
307}
308} else {
309 for (Node < E> x = first; x = null;! X = x.next) {
310 if (o.equals (x.item))
311 return index;
312 index ++;
313}
314}
315 return -1;
316}
317 // reverse search, returns the position of the first emergence of o, there is no return -1
318 public int lastIndexOf (Object o) {
319 int index = size;
320 if (o == null) {
321 for (Node < E> x = last;! X = null; x = x.prev) {
322 index--;
323 if (x.item == null)
324 return index;
325}
326} else {
327 for (Node < E> x = last;! X = null; x = x.prev) {
328 index--;
329 if (o.equals (x.item))
330 return index;
331}
332}
333 return -1;
334}
335 // Get a list of the first node element value
336 public E peek () {
337 final Node < E> f = first;
? 338 return (f == null) null: f.item;
339}
340
341 // Get a list of the first node element value, if is empty Throws
342 public E element () {
343 return getFirst ();
344}
345 // retrieve the first node, if empty returns null, not empty its element value is returned and remove the head node
346 public E poll () {
347 final Node < E> f = first;
? 348 return (f == null) null: unlinkFirst (f);
349}
350 // retrieve the first node, then throw an exception if empty, not empty its element value is returned and remove the head node
351 public E remove () {
352 return removeFirst ();
353}
354 // increase in node e end of the list
355 public boolean offer (E e) {
356 return add (e);
357}
358 // insert node e in the list header
359 public boolean offerFirst (E e) {
360 addFirst (e);
361 return true;
362}
363 // insert node e in the end of the list
364 public boolean offerLast (E e) {
365 addLast (e);
366 return true;
367}
368 public E peekFirst () {
369 final Node < E> f = first;
? 370 return (f == null) null: f.item;
371}
372 // Get a list of the tail node element values
373 public E peekLast () {
374 final Node < E> l = last;
375 return (l == null) null:? L.item;
376}
377 public E pollFirst () {
378 final Node < E> f = first;
? 379 return (f == null) null: unlinkFirst (f);
380}
381 public E pollLast () {
382 final Node < E> l = last;
383 return (l == null) null:? UnlinkLast (l);
384}
385 // stack
386 public void push (E e)
387 {
388 addFirst (e);
389}
390 // stack
391 public E pop () {
392 return removeFirst ();
393}
o 394 // node removed from the list first appears
395 public boolean removeFirstOccurrence (Object o) {
396 return remove (o);
397}
398 // reverse search, o nodes are removed from the first occurrence
399 public boolean removeLastOccurrence (Object o) {
400 if (o == null) {
401 for (Node < E> x = last;! X = null; x = x.prev) {
402 if (x.item == null) {
403 unlink (x);
404 return true;
405}
406}
407} else {
408 for (Node < E> x = last;! X = null; x = x.prev) {
409 if (o.equals (x.item)) {
410 unlink (x);
411 return true;
412}
413}
414}
415 return false;
416}
 

Third, the Instructions About LinkedList

1, pay attention to the source of the Node < E> node (int index) method:

    Node < E> node (int index)
    {
        if (index < (size >> 1))
        {
            Node < E> x = first;
            for (int i = 0; i < index; i ++)
                x = x.next;
            return x;
        }
       else
        {
            Node < E> x = last;
            for (int i = size - 1; i> index; i--)
                x = x.prev;
            return x;
        }
    }
The method returns a doubly linked list at the position specified node, but the list is not subscripted, to specify the position of the element, it is necessary to traverse the linked list, from the source to achieve, we see there is an accelerated action. Source in the first half of the length of the index compared with the size, if index < size / 2, you only traverse back from position 0 to the position of the index, and if index> size / 2, you only traverse forward from position to position size index. This can reduce unnecessary portion of traversal.

2, LinkedList and ArrayList difference:

LinkedList and ArrayList on the performance advantages and disadvantages, have their own applicable local, summarized as follows:

ArrayList is to achieve a dynamic array-based data structure, LinkedList-based linked list data structure.
LinkedList does not support efficient random access element.
Wasted space ArrayList is mainly reflected in the list at the end of the list reserve a certain capacity space, and space spending LinkedList is reflected in each of its elements need to consume considerable space on the storage density it is, is better than the LinkedList ArrayList of.
In short, when the operation is to add data later in a column of data, rather than in front or in the middle, and require random access to its elements, use ArrayList will provide better performance when your operation is in front of or in the middle of a data when you add or delete data, and access to one of the elements in the order, you should use a LinkedList.

3, LinkedList allowed elements are null

Find and delete, the source code is as follows:

public int indexOf (Object o) {
        int index = 0;
        if (o == null) {
            for (Node < E> x = first; x = null;! x = x.next) {
                if (x.item == null)
                    return index;
                index ++;
            }
        } Else {
            for (Node < E> x = first; x = null;! x = x.next) {
                if (o.equals (x.item))
                    return index;
                index ++;
            }
        }
        return -1;
    }
 
4, the use LinkedList achieve stack operation

 
public class Stack < T>
{
    private LinkedList < T> stack;
    
    // No-argument constructor
    public Stack ()
    {
        stack = new LinkedList < T> ();
    }
    // Construct a collection that contains all of the elements in the stack
    public Stack (Collection < ? extends T> c)
    {
        stack = new LinkedList < T> (c);
    }
    // Stack
    public void push (T t)
    {
        stack.addFirst (t);
    }
    // Stack
    public T pull ()
    {
        return stack.remove ();
    }
    // Stack is empty
     boolean isEmpty ()
     {
         return stack.isEmpty ();
     }
     
     // Print stack elements
     public void display ()
     {
         for (Object o: stack)
             System.out.println (o);
     }
}

Read catalog

One, HashMap Profile
Two, hashMap source code analysis
Three, HashMap Application sample code
Four, HashMap summary
One, HashMap Profile

It is based on the Map interface HashMap Hash table, which stores the contents of key-value pairs < key, value> mapped. Such mapping does not guarantee the order, assuming the hash function element proper distribution among the barrels, can provide stable performance for the basic operations (get and put).

ps: paper source from jdk1.8.0_45 / src.

1, important parameters

Examples of HashMap has two parameters that affect its performance.

Number of hash table buckets: the initial capacity

Load factor: the hash table before automatically increase its capacity up to more than a full-scale

When the number of entries in the hash table exceeds the current capacity load factor * (in fact, the actual capacity of the HashMap), then the hash table rehash operations, hash tables will expand to twice the number of barrels.

Java default initial capacity of 16, load factor of 0.75.

  static final int DEFAULT_INITIAL_CAPACITY = 1 < < 4; // aka 16
  static final float DEFAULT_LOAD_FACTOR = 0.75f;
2, HashMap inheritance

HashMap implements Coneable interface can be cloned to achieve Serializable interface, it also supports serialization.

public class HashMap < K, V>
extends AbstractMap < K, V>
implements Map < K, V>, Cloneable, Serializable
 
Two, hashMap source code analysis

1, the data structure

HashMap is actually a list of the array of structures, when a new HashMap when it initializes an array.

 
     / **
     * The table, initialized on first use, and resized as
     * Necessary. When allocated, length is always a power of two.
     * (We also tolerate length zero in some operations to allow
     * Bootstrapping mechanics that are currently not needed.)
     * /
    transient Node < K, V> [] table;
 
Type array of Node < K, V>, is defined as follows:

 
static class Node < K, V> implements Map.Entry < K, V>
    {
        final int hash;
        final K key;
        V value;
        Node < K, V> next; // next next instance of the specified list
        Node (int hash, K key, V value, Node < K, V> next)
        {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
      ....
    }
 
You can see, Node is the element in the array, and each Map.Node is a key-value pair, it holds a reference to point to the next element, which constitutes the list.

2, the constructor

HashMap has four constructors, as follows:

 
     1 // Constructor with the specified initial capacity and load factor, empty HashMap
    public HashMap (int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException ( "Illegal initial capacity:" +
                                               initialCapacity);
        if (initialCapacity> MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor < = 0 || Float.isNaN (loadFactor))
            throw new IllegalArgumentException ( "Illegal load factor:" +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor (initialCapacity);
    }
    2 // Constructor with the specified initial capacity and the default load factor (0.75) empty HashMap
    public HashMap (int initialCapacity)
    {
        this (initialCapacity, DEFAULT_LOAD_FACTOR);
    }
     // 3 construct a default initial capacity (16) and the default load factor (0.75) empty HashMap
    public HashMap ()
    {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
     // 4. construct a relationship with the same specified Map map new HashMap
    public HashMap (Map < ? extends K,? extends V> m)
    {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries (m, false);
    }
 
3, HashMap common methods

void clear (): Removes all the mappings map

 
 public void clear () // empty HashMap, all the elements of the array is set to null
    {
        Node < K, V> [] tab;
        modCount ++;
        if ((tab = table)! = null && size> 0) {
            size = 0;
            for (int i = 0; i < tab.length; ++ i)
                tab [i] = null;
        }
    }
 
Object clone (): Returns a shallow copy of this HashMap instance

 
public Object clone ()
    {
        HashMap < K, V> result;
        try
        {
            result = (HashMap < K, V>) super.clone (); // call the parent class method clone
        }
        catch (CloneNotSupportedException e) {
            // This should not happen, since we are Cloneable
            throw new InternalError (e);
        }
        result.reinitialize (); // initialize
        result.putMapEntries (this, false); // this element into HashMap result in
        return result;
    }
 
boolean containsKey (Object key): if this map contains a mapping for the specified key, it returns true.

 
public boolean containsKey (Object key)
    {
        ! Return getNode (hash (key), key) = null;
    }
    final Node < K, V> getNode (int hash, Object key) // find nodes based on hash values and key
    {
        Node < K, V> [] tab; Node < K, V> first, e; int n; K k;
        if ((tab = table)! = null && (n = tab.length)> 0 &&
            (First = tab [(n - 1) & hash])! = Null)
        {
            if (first.hash == hash && // Find the first node
                ((K = first.key) == key || (key! = Null && key.equals (k))))
                return first;
            if ((e = first.next)! = null)
            {
                if (first instanceof TreeNode)
                    return ((TreeNode < K, V>) first) .getTreeNode (hash, key);
                do {
                    if (e.hash == hash &&
                        ((K = e.key) == key || (key! = Null && key.equals (k))))
                        return e;
                } While (! (E = e.next) = null);
            }
        }
        return null;
    }
 
boolean containsValue (Object value): if this map maps one or more keys to the specified value, it returns true.

 
public boolean containsValue (Object value)
    {
        Node < K, V> [] tab; V v;
        if ((tab = table)! = null && size> 0)
        {
            for (int i = 0; i < tab.length; ++ i) // outer loop search array
            {
                for (Node < K, V> e = tab [i]; e = null;! e = e.next) // inner loop search list
                {
                    if ((v = e.value) == value ||
                        (Value! = Null && value.equals (v)))
                        return true;
                }
            }
        }
        return false;
    }
 
Set < Map.Entry < K, V >> entrySet (): Returns the mapping between this map contains a Set view that the key to return to the set

public Set < Map.Entry < K, V >> entrySet ()
    {
        Set < Map.Entry < K, V >> es;
        return (es = entrySet) == null (entrySet = new EntrySet ()):? es;
    }
get (Object key): Returns the value of the specified key is mapped; if for the key, this map contains no mapping, it returns null.

 public V get (Object key)
    {
        Node < K, V> e;
        // Find the first method by getNode node that contains the key, and then returns the node value
        ? Return (e = getNode (hash (key), key)) == null null: e.value;
    }
boolean isEmpty (): if this map contains no key - value mappings, it returns true.

 public boolean isEmpty ()
    {
        return size == 0;
    }
Set < K> keySet (): Returns the set view of the keys contained in this map, that is, the return key set

public Set < K> keySet ()
    {
        Set < K> ks;
        return (ks = keySet) == null (keySet = new KeySet ()):? ks;
    }
V put (K key, V value): In this map the specified value with the specified key.

 
 
  public V put (K key, V value)
    {
        return putVal (hash (key), key, value, false, true);
    }
    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) // node hash value that corresponds to this key is empty
            tab [i] = newNode (hash, key, value, null); // create a new node
        else
        {
            // Node is not empty, first compare the first node on the list
            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) // If the key corresponding to the key-value pair already exists, replace the old value with the new value
            {
                V oldValue = e.value;
                if (! onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess (e);
                return oldValue;
            }
        }
       // If "the key" corresponding to the key-value pair does not exist, "key-value" added to the table in
        ++ ModCount;
        // If the key-value pair after exceeding the maximum threshold, resize operation is performed
        if (++ size> threshold)
            resize ();
        afterNodeInsertion (evict);
        return null;
    }
void putAll (Map m < extends K, extends V??>): The all of the mappings specified map to this map These mappings will replace any mappings that this map for the specified map all keys

  public void putAll (Map < ? extends K,? extends V> m)
    {
        putMapEntries (m, true);
    }
V remove (Object key): Removes map maps the specified key (if it exists)

   public V remove (Object key)
    {
        Node < K, V> e;
        return (e = removeNode (hash (key), key, null, false, true)) == null?
            null: e.value;
    }
 int size (): Returns the mapping of key - value mappings number

public int size ()
    {
        return size;
    }
Collection < V> values (): Returns the value contained in this map of the Collection view

 // Returns "value set" is actually a return to the target Values
    public Collection < V> values ()
    {
        Collection < V> vs;
        return (vs = values) == null (values = new Values ()):? vs;
    }
Three, HashMap Application sample code

public class HashMapDemo
{
    public static void main (String [] args)
    {
        HashMap < String, String> hm = new HashMap < > ();
        System.out.println ( "call put function:");
        hm.put ( "01", "Amy");
        hm.put ( "02", "harry");
        hm.put ( "03", "Gary");
        hm.put ( "04", "Amy");
        HashMap < String, String> hm2 = (HashMap < String, String>) hm.clone ();
        System.out.println (hm2);
        System.out.println ( "call clear function:");
        hm2.clear ();
        System.out.println (hm2);
        System.out.println ( "call containsKey function:" + hm.containsKey ( "01"));
        System.out.println ( "call containsValue function:" + hm.containsValue ( "Amy"));
        System.out.println ( "call entrySet function:");
        Set < Entry < String, String >> result = hm.entrySet ();
        for (Entry < String, String> entry: result)
        {
            System.out.println (entry.getKey () + ":" + entry.getValue ());
        }
        
        System.out.println ( "call to get the function:" + hm.get ( "03"));
        
        System.out.println ( "call isEmpty function:" + hm.isEmpty ());
        System.out.println ( "call keySet function:");
        Set < String> kr = hm.keySet ();
        // Print all the key values
        for (String str: kr)
        {
            System.out.println (str);
        }
        System.out.println ( "call the remove function:");
        hm.remove ( "02");
        System.out.println (hm);
        System.out.println ( "call size function:" + "size =" + hm.size ());
        System.out.println ( "call the function values:");
        Collection < String> vs = hm.values ();
        for (String str: vs)
        {
            System.out.println (str);
        }
    }
}

Four, HashMap summary

HashMap is a very useful framework for the collection, respectively, can be obtained HashMap key set by the following three methods, and key-value set to set.

Keyset: Set < K> keySet ()

Value Set: Collection < K> values ()

Key-value pair set: Set < Map.Entry < K, V >> entrySet ()

The above is my summary for HashMap, due to the limited level of implementation mechanism HashMap article does not do in-depth analysis, still under study, encourage each other!

Read catalog

One, HashSet Profile
Two, HashSet source code analysis
Three, HashSet Application sample code
One, HashSet Profile

Set HashSet is a typical implementation of the interface, which according to the Hash algorithm to store elements in the collection, with good access and lookup performance. It has the following characteristics:

We do not guarantee the iteration order of the set
HashSet not synchronized, if multiple threads access a HashSet, through its synchronization code to ensure
Collection element values may be null
When the HashSet collection stored in an element, HashSet will call the object's hashCode () method to get hashCode value of the object, and then determine the object HashSet storage location based on the value. In Hash collection, can not be stored at the same time two equal elements, and determine whether the two elements are equal standards are two objects equals method compare two objects are equal and HashCode method return values are equal.

The following examples illustrate the above-mentioned features:

public class Person
{
    String name;
    int age;
    
    public Person (String name, int age)
    {
        this.name = name;
        this.age = age;
    }
    
    public String getName ()
    {
        return name;
    }

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

    public int getAge ()
    {
        return age;
    }

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

    // When the object's name and the name that is the same return true
    public boolean equals (Object obj)
    {
        if (obj == null)
            return false;
        if ((this.name.equals (((Person) obj) .name) && this.age == ((Person) obj) .age))
                return true;
        else
            return false;
    }
    
}
At this time adding two name and age are the same Person object instance to the HashSet:

public class HashSetDemo
{

    public static void main (String [] args)
    {
        HashSet < Person> hs = new HashSet < > ();
        
        Person p1 = new Person ( "xujian", 23);
        Person p2 = new Person ( "xujian", 23);
        hs.add (p1);
        hs.add (p2);
        for (Person p: hs)
        {
            System.out.println (p.name + "---" + p.age);
        }
    }
}

Visible, HashSet stored in the two name and age are the same Person object.

Next we rewrite hashCode method of Person class, it returns the same HashCode.

public class Person
{
    String name;
    int age;
    
    public Person (String name, int age)
    {
        this.name = name;
        this.age = age;
    }
    public String getName ()
    {
        return name;
    }
    public void setName (String name)
    {
        this.name = name;
    }
    public int getAge ()
    {
        return age;
    }
    public void setAge (int age)
    {
        this.age = age;
    }

    public int hashCode ()
    {
        // TODO Auto-generated method stub
        return 1;
    }
    // When the object's name and the name that is the same return true
    public boolean equals (Object obj)
    {
        if (obj == null)
            return false;
        if ((this.name.equals (((Person) obj) .name) && this.age == ((Person) obj) .age))
                return true;
        else
            return false;
    }
    
}
Perform operations while adding elements to a HashSet again, you will find at this HashSet only save one.

HashSet slots each capable of storing elements are usually referred to as "barrels", if there are multiple elements of the same hashCode, but by comparison equals method returns false, you need to store multiple elements in a barrel.

Two, HashSet source code analysis

1, the constructor

Underlying HashSet HashMap is actually implemented. Its four constructors respectively corresponding HashMap.

  // Construct a new, empty HashSet, the default initial capacity of the backing HashMap instance is 16, load factor is 0.75
    public HashSet ()
    {
        map = new HashMap < > ();
    }

    // Construct a new set of elements in the specified collection contains
    public HashSet (Collection < ? extends E> c)
    {
        map = new HashMap < > (Math.max ((int) (c.size () / 75f) + 1, 16).);
        addAll (c);
    }

   // Construct a new, empty set, the backing HashMap instance has the specified initial capacity and the specified load factor
    public HashSet (int initialCapacity, float loadFactor) {
        map = new HashMap < > (initialCapacity, loadFactor);
    }

    // Construct a new, empty set, the backing HashMap instance has the specified initial capacity and default load factor 0.75
    public HashSet (int initialCapacity)
    {
        map = new HashMap < > (initialCapacity);
    }
 
2, HashSet common method

boolean add (E e): if this set contains the specified element is not already, add the specified element

public boolean add (E e)
    {
        // Call the put map, wherein the value is static Object object
        return map.put (e, PRESENT) == null;
    }
void clear (): Removes all of the elements in the set

 public void clear ()
    {
        map.clear ();
    }
Object clone (): Returns a shallow copy of this HashSet instance

 
 public Object clone ()
    {
        try
        {
            // Call the parent class method clone
            HashSet < E> newSet = (HashSet < E>) super.clone ();
            newSet.map = (HashMap < E, Object>) map.clone ();
            return newSet;
        }
        catch (CloneNotSupportedException e)
        {
            throw new InternalError (e);
        }
    }
 
boolean contains (Object o): if this set contains the specified elements, returns true

public boolean contains (Object o)
    {
        return map.containsKey (o);
    }
boolean isEmpty (): if this set contains no elements, returns true

public boolean isEmpty ()
    {
        return map.isEmpty ();
    }
Iterator < E> iterator (): Returns the elements in this set iterator

 public Iterator < E> iterator ()
    {
        return map.keySet () iterator ().;
    }
boolean remove (Object o): If specified element from this set, it is removed

 public boolean remove (Object o)
    {
        return map.remove (o) == PRESENT;
    }
int size (): Returns the number of elements in the set

    public int size ()
    {
        return map.size ();
    }
Three, HashSet Application sample code

public class HashSetDemo
{
    public static void main (String [] args)
    {
        HashSet < String> hs1 = new HashSet < > (); // no-argument constructor to create a new default size is 16, the load factor of 0.75 HashSet
        System.out.println ( "call the add function");
        hs1.add ( "Hello");
        hs1.add ( "World");
        hs1.add ( "nihao");
        
        HashSet < String> hs2 = new HashSet < > (hs1); // construct containing the elements of a HashSet hs1
        
        System.out.println ( "call the remove function");
        hs1.remove ( "Hello");
        for (String str: hs1)
            System.out.println (str);
    
        System.out.println ( "call the clone function");
        HashSet < String> hs3 = (HashSet < String>) hs2.clone ();
        for (String str: hs3)
            System.out.println (str);
        
        System.out.println ( "iterative traversal HashSet elements");
        Iterator < String> it = hs2.iterator ();
        while (it.hasNext ())
        {
            System.out.println (it.next ());
        }
        
        System.out.println ( "call size function");
        
        System.out.print (hs2.size ());
    }
}

Read catalog

One, overview
Two, TreeMap source code analysis
Three, TreeMap application sample code
One, overview

TreeMap is based on the red-black tree implementation. Since TreeMap implements java.util.sortMap interface mapping between the collection is a certain order, which is ordered according to the natural ordering of its keys or the provided at map creation Comparator to sort, depending on which constructor is used . Also not allowed TreeMap key object is null.

1. What is a red-black tree?

Red-black tree is a special binary sort tree, mainly in the following several basic properties:

Each node can be red or black
The root node is black
Each leaf node is black
If a node is red, then both its child nodes are black
All paths from any node to each leaf node contains the same number of black nodes

2, key two sort

Natural Sort: All key TreeMap must implement the Comparable interface, and all the key should be the same type of object, otherwise it will throw a ClassCastException

Specify the sort: the sort required in the construction of this TreeMap, pass a Comparator object that is responsible for the TreeMap sort of key

3, the class inheritance relationship TreeMap

public class TreeMap < K, V>

extends AbstractMap < K, V>

implements NavigableMap < K, V>, Cloneable, Serializable
Wherein, NavigableMap the interface is extended SortMap, it has a target for a given search returns the closest match of the navigation system. The methods lowerEntry, floorEntry, ceilingEntry and higherEntry returns respectively less than, less than or equal, greater than or equal, greater than the given key Map.Entry objects associated with the key, if there is no such key, returns null. Similarly, the method lowerKey, floorKey, ceilingKey and higherKey only returns the associated key. All of these methods is to look for an entry rather than traversing the entry and design.

Two, TreeMap source code analysis

1, the storage structure

TreeMap is a node-based definition of red-black tree implementation of the tree is as follows:

 static final class Entry < K, V> implements Map.Entry < K, V>
    {
        //key
        K key;
        //value
        V value;
        // Left child
        Entry < K, V> left;
        // Right child
        Entry < K, V> right;
        // Parent node
        Entry < K, V> parent;
        // Node color
        boolean color = BLACK;
        //Constructor
        Entry (K key, V value, Entry < K, V> parent)
        {
            this.key = key;
            this.value = value;
            this.parent = parent;
        }
        ......
}
2, the constructor

TreeMap four constructors, corresponding to different parameters.

   // 1. Use keys natural ordering construction of a new, empty tree map
    public TreeMap ()
    {
        comparator = null;
    }
    // 2. Construct a new, empty tree map, according to the given comparator sort
    public TreeMap (Comparator < ? super K> comparator)
    {
        this.comparator = comparator;
    }
    / 3 construct a given map with the new tree map containing the same mappings, the map sorted according to the natural ordering of its keys
    public TreeMap (Map < ? extends K,? extends V> m)
    {
        comparator = null;
        putAll (m);
    }
    The new tree map // 4. Construct a specified sorted map with the same mappings and using the same sort order
    public TreeMap (SortedMap < K,? extends V> m)
    {
        comparator = m.comparator ();
        try
        {
            buildFromSorted (m.size (), m.entrySet () iterator (), null, null.);
        }
        catch (java.io.IOException cannotHappen)
        {
        }
        catch (ClassNotFoundException cannotHappen)
        {
        }
    }
 
3, TreeMap common methods

V put (K key, V value): The key-value pair (key, value) added to the TreeMap

public V put (K key, V value)
    {
        Entry < K, V> t = root;
        // If the root node is empty, places (key, value) as a parameter New Node
        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
        < ? Super K> Comparator cpr = comparator; // specify the sorting algorithm
        if (cpr! = null)
        {
            do {
                parent = t;
                cmp = cpr.compare (key, t.key);
                if (cmp < 0) // indicates the new node and the current node key less than key, places the left child of the current node as the new current node
                    t = t.left;
                else if (cmp> 0) // node represents key new key is greater than the current node and, places the right child of the current node as the new current node
                    t = t.right;
                else
                    return t.setValue (value); // value equal to overwrite old
            } While (t = null!);
        }
        // If cpr is empty, then use the default sorting algorithm to create a TreeMap collection
        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!);
        }
        // The new node as a child node of the parent
        Entry < K, V> e = new Entry < > (key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
      // Insert a new node after calling fixAfterInsertion adjustment red-black tree
        fixAfterInsertion (e);
        size ++;
        modCount ++;
        return null;
    }
Set < Map.Entry < K, V >> entrySet (): Returns the mapping between this map included in the Set View

    public Set < Map.Entry < K, V >> entrySet ()
     {
        EntrySet es = entrySet;
        ? Return (! Es = null) es: (entrySet = new EntrySet ());
    }
boolean remove (Object o): If the mapping for this key from this TreeMap if deleted

public boolean remove (Object o)
{
                if (! (o instanceof Map.Entry))
                    return false;
                Map.Entry < K, V> entry = (Map.Entry < K, V>) o;
                K key = entry.getKey ();
                if (! inRange (key))
                    return false;
                TreeMap.Entry < K, V> node = m.getEntry (key);
                if (node! = null && valEquals (node.getValue (),
                                            entry.getValue ()))
               {
                    m.deleteEntry (node);
                    return true;
                }
                return false;
            }
}
Three, TreeMap application sample code

public class TreeMapDemo
{
    public static void main (String [] args)
    {
        // Use the natural ordering of the keys to construct a new, empty tree map
        TreeMap < String, String> tm = new TreeMap < > ();
        tm.put ( "001", "China");
        tm.put ( "003", "United States");
        tm.put ( "002", "French");
        System.out.println ( "call entrySet get the key to set:");
        Set < Entry < String, String >> result = tm.entrySet ();
        for (Entry < String, String> result2: result)
        {
            System.out.println (result2.getKey () + "---" + result2.getValue ());
        }
        System.out.println ( "call keySet receive keyset:");
        Set < String> result3 = tm.keySet ();
        for (String str: result3)
        {
            System.out.println (str);
        }
        System.out.println ( "call to get the value set of values:");
        Collection result4 = tm.values ();
        for (Object str: result4)
            System.out.println (str);
        
        // Create a new TreeMap with a Comparator
        TreeMap < String, String> tm2 = new TreeMap < > (new ComparatorDemo ());
        tm2.put ( "001", "China");
        tm2.put ( "003", "United States");
        tm2.put ( "002", "French");
        Set < Entry < String, String >> result5 = tm2.entrySet ();
        for (Entry < String, String> result2: result5)
        {
            System.out.println (result2.getKey () + "---" + result2.getValue ());
        }
    }
}
First, according to the natural ordering of its keys to build TreeMap, added elements and traverse:

Then create a comparator class that implements Comparator interface

public class ComparatorDemo implements Comparator < String>
{

    public int compare (String o1, String o2) {
        return 1;
    }

}
In tm2 with comparator in accordance with the same procedure tm1 add elements, then traversing tm2

Here is the order in accordance with comparators compare methods come. Since the compare method always returns 1, which are the same size, so the key sequence tm2 initial order of addition.
     
         
       
         
  More:      
 
- Oracle common internal event tracking number (Database)
- How to deploy Python Web application: Heroku deployment process complete records (Server)
- Asynchronous JavaScript loading (Programming)
- Linux system Iptables Firewall User Manual (Linux)
- Redis data types Introduction (Database)
- How to generate Linux, random password encryption or decryption (Linux)
- Ubuntu and derived versions of the user how to install G Mic 1.5.8.5 (Linux)
- To remove those IP is prohibited Fail2ban on CentOS 6/7 (Server)
- Android Notification (Programming)
- The top command under Linux (Linux)
- Use OpenSSL for RSA encryption and decryption (Linux)
- Docker Private Registry Installation Guide at CentOS6.X (Linux)
- In Spring AOP example explanation (Programming)
- MySQL high availability cluster fragmentation of deployment uses Cobar (Database)
- Solaris 10 installation configuration mrtg monitoring system (Linux)
- blecat: Bluetooth Gadgets (Linux)
- Definition Format Oracle basis of various statements (Database)
- Hyper-V virtual hard disk how to copy files to and attached to the virtual machine (Linux)
- Modify MySQL character encoding under Linux (Database)
- Binary tree traversal algorithm summary (recursive and non-recursive) (Programming)
     
           
     
  CopyRight 2002-2016 newfreesoft.com, All Rights Reserved.