http://stackoverflow.com/questions/14750374/what-is-complexity-of-size-for-treeset-portion-view-in-java
http://stackoverflow.com/questions/10706589/what-is-the-time-complexity-of-the-tailset-operation-of-java-util-treeset
Small clarification: tailSet(), headSet() and subSet() return very small objects that delegate all the hard work to methods of the underlying set. No new set is constructed. Hence O(1) and pretty insignificant.
SortedMap
NavigableMap extends SortedMap
NavigableMap:
NavigableMap<K,V> headMap(K toKey, boolean inclusive);
SortedMap<K,V> headMap(K toKey); // why not return NavigableMap?
public interface SortedMap<K,V> extends Map<K,V> {
SortedMap<K,V> headMap(K toKey);
1
---
3
4
5
1
------
3
4
5
public class ArrayDeque<E> extends AbstractCollection<E>
implements Deque<E>, Cloneable, Serializable
{
transient Object[] elements; // non-private to simplify nested class access
// The index of the element at the head of the deque (which is the
// element that would be removed by remove() or pop()); or an
// arbitrary number equal to tail if the deque is empty.)
transient int head;
// The index at which the next element would be added to the tail
transient int tail;
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
public E pollFirst() {
int h = head;
@SuppressWarnings("unchecked")
E result = (E) elements[h];
// Element is null if deque empty
if (result == null)
return null;
elements[h] = null; // Must null out slot
head = (h + 1) & (elements.length - 1);
return result;
}
public E pollLast() {
int t = (tail - 1) & (elements.length - 1);
@SuppressWarnings("unchecked")
E result = (E) elements[t];
if (result == null)
return null;
elements[t] = null;
tail = t;
return result;
}
public E getFirst() {
@SuppressWarnings("unchecked")
E result = (E) elements[head];
if (result == null)
throw new NoSuchElementException();
return result;
}
public E getLast() {
@SuppressWarnings("unchecked")
E result = (E) elements[(tail - 1) & (elements.length - 1)];
if (result == null)
throw new NoSuchElementException();
return result;
}
}
http://stackoverflow.com/questions/36825213/why-the-arraydeque-class-use-bitwise-operation-in-the-pollfirst-method
TreeSet:
Taking the tailSet is O(log n), but iterating over the the last
How to reset ArrayList in Java - Clear vs RemoveAll
You should always use clear(), because it gives you O(n) performance, while removeAll(Collection c) is worse, it gives O(n^2)performance.
-- But why we should call list.removeAll(list)?
the method Arrays.asList(T…a) returns an ArraysList that doesn’t implement the add or remove method (as it says in the specs is fixed size list), so trying to do something like this:
String[] fooArray = {"one", "two", "three"};
List<String> fooList = Arrays.asList(fooArray);
fooList.add("four");
We get an UnsupportedOperationException. Quick fix for this is initialize a mutable list passing the immutable list returned by the method:
List<String> fooList= new ArrayList<String>(Arrays.asList(fooArray));
It’s not an immutable List that is returned. Methods that don’t change the size of the list are supported, e.g. set.
http://stackoverflow.com/questions/16992758/is-there-a-bug-in-java-util-stacks-iterator
1) void add(E e): Inserts the specified element into the list (optional operation).
2) boolean hasNext(): Returns true if this list iterator has more elements when traversing the list in the forward direction.
3) boolean hasPrevious(): Returns true if this list iterator has more elements when traversing the list in the reverse direction.
4) E next(): Returns the next element in the list and advances the cursor position.
5) int nextIndex(): Returns the index of the element that would be returned by a subsequent call to next().
6) E previous(): Returns the previous element in the list and moves the cursor position backwards.
7) int previousIndex(): Returns the index of the element that would be returned by a subsequent call to previous().
8) void remove(): Removes from the list the last element that was returned by next() or previous() (optional operation).
9) void set(E e): Replaces the last element returned by next() or previous() with the specified element (optional operation).
http://stackoverflow.com/questions/18995038/what-does-list-iterators-add-method-do-to-the-iterator
https://www.deadend.me/2016/07/18/difference-between-fail-fast-and-fail-safe-in-java/
Looks like complexity of
size () is O(N), because it may call TreeMap.NavigableSubMap.EntrySetView.size () which is implemented like this (Oracle JDK 1.7.0_13):public int size() {
if (fromStart && toEnd)
return m.size();
if (size == -1 || sizeModCount != m.modCount) {
sizeModCount = m.modCount;
size = 0;
Iterator i = iterator();
while (i.hasNext()) {
size++;
i.next();
}
}
return size;
}
AFAIK Taking the tailSet is O(log n), but iterating over the the last
m elements is O(m * log n)Small clarification: tailSet(), headSet() and subSet() return very small objects that delegate all the hard work to methods of the underlying set. No new set is constructed. Hence O(1) and pretty insignificant.
SortedMap
NavigableMap extends SortedMap
NavigableMap:
NavigableMap<K,V> headMap(K toKey, boolean inclusive);
SortedMap<K,V> headMap(K toKey); // why not return NavigableMap?
public interface SortedMap<K,V> extends Map<K,V> {
SortedMap<K,V> headMap(K toKey);
public static void main(String[] args) { TreeSet<Integer> set = new TreeSet(); set.add(1); set.add(2); set.add(3); set.add(4); set.add(5); // set.headSet(3) NavigableSet<Integer> head = ((NavigableSet)set.headSet(3)).descendingSet(); for(Integer i : head) { System.out.println(i); } System.out.println("---"); for(Integer i: set.tailSet(3)) { System.out.println(i); } }2
1
---
3
4
5
TreeMap<Integer, Integer> map = new TreeMap<>(); map.put(1,1);map.put(2,2);map.put(3,3);map.put(4,4); map.put(5,5); final NavigableMap<Integer, Integer> headMap = ((NavigableMap<Integer, Integer>) map.headMap(3)).descendingMap(); for(Integer i: headMap.values()) { System.out.println(i);} System.out.println("------");for(Integer i: map.tailMap(3).values()) { System.out.println(i);}2
1
------
3
4
5
public class ArrayDeque<E> extends AbstractCollection<E>
implements Deque<E>, Cloneable, Serializable
{
transient Object[] elements; // non-private to simplify nested class access
// The index of the element at the head of the deque (which is the
// element that would be removed by remove() or pop()); or an
// arbitrary number equal to tail if the deque is empty.)
transient int head;
// The index at which the next element would be added to the tail
transient int tail;
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
public E pollFirst() {
int h = head;
@SuppressWarnings("unchecked")
E result = (E) elements[h];
// Element is null if deque empty
if (result == null)
return null;
elements[h] = null; // Must null out slot
head = (h + 1) & (elements.length - 1);
return result;
}
public E pollLast() {
int t = (tail - 1) & (elements.length - 1);
@SuppressWarnings("unchecked")
E result = (E) elements[t];
if (result == null)
return null;
elements[t] = null;
tail = t;
return result;
}
public E getFirst() {
@SuppressWarnings("unchecked")
E result = (E) elements[head];
if (result == null)
throw new NoSuchElementException();
return result;
}
public E getLast() {
@SuppressWarnings("unchecked")
E result = (E) elements[(tail - 1) & (elements.length - 1)];
if (result == null)
throw new NoSuchElementException();
return result;
}
}
http://stackoverflow.com/questions/36825213/why-the-arraydeque-class-use-bitwise-operation-in-the-pollfirst-method
Take a look at the initialization code - the Deque is represented as an array whose size is always a power of 2:
195 public ArrayDeque(int numElements) {
196 allocateElements(numElements);
197 }
124 private void allocateElements(int numElements) {
125 int initialCapacity = MIN_INITIAL_CAPACITY;
126 // Find the best power of two to hold elements.
127 // Tests "<=" because arrays aren't kept full.
128 if (numElements >= initialCapacity) {
129 initialCapacity = numElements;
130 initialCapacity |= (initialCapacity >>> 1);
131 initialCapacity |= (initialCapacity >>> 2);
132 initialCapacity |= (initialCapacity >>> 4);
133 initialCapacity |= (initialCapacity >>> 8);
134 initialCapacity |= (initialCapacity >>> 16);
135 initialCapacity++;
136
137 if (initialCapacity < 0) // Too many elements, must back off
138 initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
139 }
140 elements = (E[]) new Object[initialCapacity];
141 }
so
elements.length - 1 is binary is basically a series of 1 bits before the size of the array is exceeded.
For instance, if
elements is initialized to an array of size 16, then elements.length - 1 is 15, meaning 0..001111 (truncated leading zeros).
So when the
head element is reset in pollFirst method (advanced by one), the bitwise &operator is used in order to make the Deque cyclic. Again, if elements is of size 16 and currently head is 15, then head + 1 would be 16, and so:10000
01111
-----
00000
Meaning, the
head is reset to index 0. This allows you to reuse the space you've already allocated, using the array and its O(1) efficiency in inserting and retrieval, without needing to allocate new space.
The same is true for
pollLast where you reset the tail variable, i.e. if tail is 0 and elementsis of size 16, then:tail 00000
tail-1 11111 (-1 in two's complement)
01111
-----
01111
Meaning
tail is decremented one value, but moves from 0 to elements.length - 1.
You could have achieved the same with a more "complex" if statement (or by using the trinary operator), however this is a fairly common and acceptable way of implementing a cyclic array.
It's a more efficient way of calculating
(head+1) % elements.length, which we can do because elements.length is a power of 2. It is more efficient because the mod operator is expensive compared to bitwise and.
On the other end, only using mod for the
tail would not work because in Java, -1 % N == -1.TreeSet:
public SortedSet<E> subSet(E fromElement, E toElement) {
return subSet(fromElement, true, toElement, false);
}
public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
E toElement, boolean toInclusive) {
return new TreeSet<>(m.subMap(fromElement, fromInclusive,
toElement, toInclusive));
}
public NavigableSet<E> headSet(E toElement, boolean inclusive) {
return new TreeSet<>(m.headMap(toElement, inclusive));
}
public SortedSet<E> headSet(E toElement) {
return headSet(toElement, false);
}
lower/floor/higher/ceiling
The last() method of java.util.TreeSet class will return the last (highest) element currently in this set whereas lower(E e) method returns the greatest element in this set strictly less than the given element, or null if there is no such element.
http://www.javainterviewpoint.com/java-treeset-floore-e-example/
We have already seen first() method ofjava.util.TreeSet class which will return the first (lowest) element currently in this set whereas floor()method returns the greatest element in the set lessthan or equal to the given element, or null if there is no such element.
treesubset=(TreeSet)treeadd.subSet(3, true, 7, true);
System.out.println(set.tailSet("C")); System.out.println(set.headSet("C"));http://tientadinh.blogspot.com/2009/06/binary-search-tree-feature-with-treeset.html
Now if k is not in the set, one may wish to find the elements immediately on the left and right of k in the set. In other words, the result would be the same as executing binarySearch() method on the ordered list of all the elements in the set. The most efficient way I found in doing that is as follows:
These will have run-time complexity of O(logN) without introducing any other datastructure (or extra memory). I've experimented with other methods such as using Iterator on the set, or ArrayList, but they all appear inferior. The reason for this efficiency seems to be the fact that eventhough headSet(k) and tailSet(k) return subsets, elements of which are only computed while using Iterators to access them. Thus, calling last() and first() on these subsets are O(1). The O(logN) comes from the search for key k, a side-effect of which are pointers to these subsets.
left = set.headSet(k).last();
right = set.tailSet(k).first();These will have run-time complexity of O(logN) without introducing any other datastructure (or extra memory). I've experimented with other methods such as using Iterator on the set, or ArrayList, but they all appear inferior. The reason for this efficiency seems to be the fact that eventhough headSet(k) and tailSet(k) return subsets, elements of which are only computed while using Iterators to access them. Thus, calling last() and first() on these subsets are O(1). The O(logN) comes from the search for key k, a side-effect of which are pointers to these subsets.
Taking the tailSet is O(log n), but iterating over the the last
m elements is O(m * log n)How to reset ArrayList in Java - Clear vs RemoveAll
You should always use clear(), because it gives you O(n) performance, while removeAll(Collection c) is worse, it gives O(n^2)performance.
-- But why we should call list.removeAll(list)?
public void clear() { modCount++; // clear to let GC do its work for (int i = 0; i < size; i++) elementData[i] = null; size = 0; }
public boolean removeAll(Collection c) { boolean modified = false; Iterator it = iterator(); while (it.hasNext()) { if (c.contains(it.next())) { it.remove(); modified = true; } } return modified; }http://jasalguero.com/ledld/development/java/java-arrays-aslist-returns-immutable-list/
the method Arrays.asList(T…a) returns an ArraysList that doesn’t implement the add or remove method (as it says in the specs is fixed size list), so trying to do something like this:
String[] fooArray = {"one", "two", "three"};
List<String> fooList = Arrays.asList(fooArray);
fooList.add("four");
We get an UnsupportedOperationException. Quick fix for this is initialize a mutable list passing the immutable list returned by the method:
List<String> fooList= new ArrayList<String>(Arrays.asList(fooArray));
It’s not an immutable List that is returned. Methods that don’t change the size of the list are supported, e.g. set.
http://stackoverflow.com/questions/16992758/is-there-a-bug-in-java-util-stacks-iterator
See Bug ID 4475301 : RFE: java.util.Stack.iterator() iterates the wrong way. This behavior is by (bad) design. Java's built-in
Stack iterator methods are inherited from other classes, so they don't behave as you'd expect.2) boolean hasNext(): Returns true if this list iterator has more elements when traversing the list in the forward direction.
3) boolean hasPrevious(): Returns true if this list iterator has more elements when traversing the list in the reverse direction.
4) E next(): Returns the next element in the list and advances the cursor position.
5) int nextIndex(): Returns the index of the element that would be returned by a subsequent call to next().
6) E previous(): Returns the previous element in the list and moves the cursor position backwards.
7) int previousIndex(): Returns the index of the element that would be returned by a subsequent call to previous().
8) void remove(): Removes from the list the last element that was returned by next() or previous() (optional operation).
9) void set(E e): Replaces the last element returned by next() or previous() with the specified element (optional operation).
http://stackoverflow.com/questions/18995038/what-does-list-iterators-add-method-do-to-the-iterator
Read the ListIterator#add()
A simple example:
public static void main(String args []){
List<String> list= new ArrayList<String>();
list.add("hi");
list.add("whats up");
list.add("how are you");
list.add("bye");
ListIterator<String> iterator = list.listIterator();
int i=0;
while(iterator.hasNext()){
String s = iterator.next();
iterator.add(""+i++);
}
System.out.println(list);
//output: [hi, 0, whats up, 1, how are you, 2, bye, 3]
}https://www.deadend.me/2016/07/18/difference-between-fail-fast-and-fail-safe-in-java/
fail-fast机制在遍历一个集合时，当集合结构被修改，会抛出
ConcurrentModificationException。Collection中所有Iterator的实现都是按fail-fast来设计的(ConcurrentHashMap和CopyOnWriteArrayList这类并发集合类除外)。 fail-fast会在以下两种情况下抛出ConcurrentModificationException- 单线程环境：集合被创建后，在遍历它的过程中修改了结构，比如iterator的remove方法
- 多线程环境：当一个线程在遍历这个集合，而另一个线程对这个集合的结构进行了修改
fail-fast机制检测原理
为了保证在遍历中集合不被修改，集合内部和迭代器内部同时维护了各自的标记
modCount和expectedModCount。当集合结构改变（添加删除或者修改）时，modCount会被修改（大多时候是加1），而迭代器每次调用next()方法都会检查两个标记是否一致，不一致时就会抛出ConcurrentModificationException异常。
以
ArrayList源码为例，其内部迭代器实现简化如下// Java 7
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
... // 省略
}
public void remove() {
... // 省略
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
fail-safe机制
fail-safe机制中任何对集合结构的修改都会在一个复制的集合上进行，因此不会抛出
ConcurrentModificationException。但fail-safe机制存在两个问题：- 复制集合会产生大量的无效对象，开销大
- 无法保证读取的数据是目前原始数据结构中的数据
fail-fast机制与fail-safe机制对比
java.util包中的所有集合类都被设计为fail-fast的，而java.util.concurrent中的集合类都为fail-safe的。| 方面 | Fail Fast Iterator | Fail Safe Iterator |
|---|---|---|
抛出ConcurrentModificationException异常 | 是 | 否 |
| 复制对象 | 否 | 是 |
| 耗费内存 | 否 | 是 |
| 举例 | HashMap,Vector,ArrayList,HashSet | CopyOnWriteArrayList, ConcurrentHashMap |
