前言
本周是学习java的第五周，粗略的学习了一下hashmap的底层实现原理。
参考教程：
本周学习要点：
1.ArrayList在查询较多时使用到，一般较多使用到它。
2.LinkList在增删较多时使用到。
3.Vector线程安全，但相对的效率低，而且并不是安全就是好的。
4.HashMap是键值对，是map接口的实现类。put方法中，键不能重复，否则会覆盖掉旧的。
5.HashMap底层是结合数组和链表实现的，具有数组的查询快的优点和链表的增加和删除快的优点
6.在jdk1.8版本后，java对HashMap做了改进，在链表长度大于8的时候，将后面的数据存在红黑树中，以加快检索速度
7.<< >>相当于对该数作乘或除2的操作，比使用符号运算速度快。
哈希表
也叫散列表，是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。
若关键字为k，则其值存放在f(k)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数，按这个思想建立的表为散列表。
对不同的关键字可能得到同一散列地址，即k1≠k2，而f(k1)=f(k2)，这种现象称为冲突（英语：Collision）。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数f(k)和处理冲突的方法将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为散列表，这一映射过程称为散列造表或散列，所得的存储位置称散列地址。
若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数（Uniform Hash function），这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。——百度百科
从图片中很轻易看出来就是数组和链表的结合。
java中的hashmap会先定义一个node:
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
它是Map.Entry接口的一个实现类，其内还有一些set，get方法和toString方法等等。然后就是数组，数组默认是一个长度为16的数组，当其内元素被占用超过0.75也就是12时，会扩容。对于链表，在链表长度大于8的时候，将后面的数据存在红黑树中，红黑树的平均查找长度是log(n)，如果长度为8，平均查找长度为log(8)=3，链表的平均查找长度为n/2，当长度为8时，平均查找长度为8/2=4，这才有转换成树的必要；链表长度如果是小于等于6，6/2=3，而log(6)=2.6，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。
哈希函数
在我目前理解中，java的hashmap中，是将key的hashcode传入后经过哈希函数运算出一个数字作为该键值对在数组中的地址，当数据量大时会产生冲突，一个均匀的哈希函数可以减少冲突但不能避免冲突，所以需要解决冲突的方法。
红黑树
红黑树就是一种平衡的二叉查找树，说他平衡的意思是他不会变成“瘸子”，左腿特别长或者右腿特别长。除了符合二叉查找树的特性之外，还具体下列的特性：
- 节点是红色或者黑色
- 根节点是黑色
- 每个叶子的节点都是黑色的空节点（NULL）
- 每个红色节点的两个子节点都是黑色的。
- 从任意节点到其每个叶子的所有路径都包含相同的黑色节点。
其在c语言中的简单定义如下:
#define RED 0 // 红色节点
#define BLACK 1 // 黑色节点
typedef int Type;
// 红黑树的节点
typedef struct RBTreeNode{
unsigned char color; // 颜色(RED 或 BLACK)
Type key; // 关键字(键值)
struct RBTreeNode *left; // 左孩子
struct RBTreeNode *right; // 右孩子
struct RBTreeNode *parent; // 父结点
}Node, *RBTree;
// 红黑树的根
typedef struct rb_root{
Node *node;
}RBRoot;
