# JavaGuide
## HashMap
###
###
#### DEFAULT_INITIAL_CAPACITY
```java
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 >> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
`int n = cap - 1`cap2
cap 2 `int n = cap - 1` cap cap 1632 16 cap232
| 001.
`cap`=10
int n = cap - 1; > 9
n |= n >>> 1;
00000000 00000000 00000000 00001001 9
00000000 00000000 00000000 00000100 9 >>> 1 1
---------------------------------------------
00000000 00000000 00000000 00001101 |= 13
n = 13
n |= n >>> 2;
00000000 00000000 00000000 00001101 13
00000000 00000000 00000000 00000011 n >>> 2
---------------------------------------------
00000000 00000000 00000000 00001111 |= 15
n = 15
n |= n >>> 4;
00000000 00000000 00000000 00001111 15
00000000 00000000 00000000 00000000 n >>> 4
---------------------------------------------
00000000 00000000 00000000 00001111 |= 15
... ...
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
```
#### DEFAULT_LOAD_FACTOR
```java
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 0.7575%
```
#### MAXIMUM_CAPACITY
```java
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two = MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// oldCap Node3
hiHeadNode2
*/
next = e.next;
// 0
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 1( + )
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// loHeadhiHead
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
```
### remove()
6
```java
public V remove(Object key) {
Node e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
```
```java
final Node removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
Node[] tab; Node p; int n, index;
// hash
if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {
Node node = null, e; K k; V v;
// key node
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
node = p;
// key
else if ((e = p.next) != null) {
//
if (p instanceof TreeNode)
node = ((TreeNode)p).getTreeNode(hash, key);
//
else {
do {
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
node = e;
break;
}
// p p.next = node.next; key
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) {
//
if (node instanceof TreeNode)
((TreeNode)node).removeTreeNode(this, tab, movable);
// tab[index] = null
else if (node == p)
tab[index] = node.next;
//
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
```
### get()
```java
public V get(Object key) {
Node e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
```
```java
final Node getNode(int hash, Object key) {
Node[] tab; Node first, e; int n; K k;
// hash
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
// first.hash == hashalways check first node
//
if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
return first;
//
if ((e = first.next) != null) {
//
if (first instanceof TreeNode)
return ((TreeNode)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;
}
```
`get()`
1. hash key
2. key key
3. key key
1. key value
2. key value
## ArrayList
###
###
#### DEFAULT_CAPACITY
```java
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
```
#### EMPTY_ELEMENTDATA
```java
/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
```
#### DEFAULTCAPACITY_EMPTY_ELEMENTDATA
```java
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
```
#### elementData
```java
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested class access
```
#### size
```java
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;
```
#### MAX_ARRAY_SIZE
```java
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
```
### add()
```java
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return true (as specified by {@link Collection#add})
*/
public boolean add(E e) {
//
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
//
private void ensureExplicitCapacity(int minCapacity) {
// modCount++;
modCount++;
// overflow-conscious code
//
if (minCapacity - elementData.length > 0)
//
grow(minCapacity);
}
```
add(index, element) index check
```java
public void add(int index, E element) {
rangeCheckForAdd(index);
// add(element)
ensureCapacityInternal(size + 1); // Increments modCount!!
//
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
```
`addAll(Collection