关于集合与HashMap

???? 我们最开始接触编程的时候第一次使用的数据结构应该都是数组，数组是一块连续的内存的统称，如果拆开来看，那么就是一个一个的变量。数组的内存是静态分配的，也就是给一个数组开辟一块内存之后不能改变其大小。其实数组是变量(数据)和数字（索引）的关联，连续的内存决定数组的查找迅速，但对于删除、添加等操作则上十分麻烦。在此基础上，我们接触了java中的容器类：Map、Collection 、Iterator等接口，对于java的核心结合框架：Set、List、Map，简单的归纳如下：

List
LinkedList:对顺序访问做了优化，可以提供队列、双向队列、栈的功能
ArrayKList：一个用数组实现的List。能进行快速的随机访问，但是往列表中间插入和删除元素的时候比较慢
Set
LinkedHashSet在内部用散列来提高查询速度，但是它看上去像是用链表来保存元素的插入顺序的
HashSet:为优化查询速度而设计的Set，采用的数据结构是“专为快速查找而设计”的散列函数;
TreeSet：是一个有序的Set，其底层是一颗树。这样你就能从Set里面提取一个有序序列了,采用的是红黑树的数据结构为元素排序;
LinkedHashSet(JDK 1.4)：一个在内部使用链表的Set，既有HashSet的查询速度，又能保存元素被加进去的顺序（插入顺序），LinkedHashSet在内部用散列来提高查询速度;
HashSet提供了最快的查询速度。而TreeSet则保持元素有序。LinkedHashSet保持元素的插入顺序。
Map
HashMap:采用哈希码算法，以便快速查找一个键值
关于哈希码算法：
?1：Object类的hashCode.返回对象的内存地址经过处理后的结构，由于每个对象的内存地址都不一样，所以哈希码也不一样。
?2：String类的hashCode.根据String类包含的字符串的内容，根据一种特殊算法返回哈希码，只要字符串内容相同，返回的哈希码也相同。
?3：Integer类，返回的哈希码就是Integer对象里所包含的那个整数的数值
TreeMap：用树的数据结构对键值进行了排序

其实弄懂了每个类型的数据结构的内部数据保存方式，那么对它的操作也就知道了，例如用数组就知道查找快而删除添加缓慢，用链表就知道删除添加迅速而查找不如数组那么快，当然，处理数组和链表之外，我们还有一种数据结构-------Map，键值对存储数据。让我们先看一下HashSet的构造器

?? 
?在用构造器1的时候，由于
while (capacity < initialCapacity) capacity <<= 1; 
?所以不管我们输入的创建Map的大小是多少，HashMap创建的Entry[]将是刚刚大于我们传入的数的2的整数次幂，这样有什么好处？我们再看一下HashMap的关于确定一个Entry保存位置的函数
?
int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); static int indexFor(int h, int length) { return h & (length-1); } 
?i就是计算得出来的索引位置，也就是该对象的Hash码与表的大小-1相与的结果，刚开始对length-1很不理解，后来才知道这样是为了提供HashMap的效率。因为length是2的整数次幂，那么length的二进制表示就是：10000000......（指数个0），那么length-1就是1111......（指数个1），任何数与length-1相与之后仍然是原来的数，这样就能保证分布均匀，尽量减少了哈希冲突。
?
?
?构造器2建立在构造器1的基础上，构造器3采用默认的参数，构造器4在一个已经建立好的HashMap上新建一个HashMap。
当我们创建好HashMap对象之后，肯定是要往里面保存东西的，那么HashMap是怎么做的呢？关于添加的方法，HashMap如下：
  

哈哈。。如果有一个对所有数据类型都很实用的哈希函数的话，估计不会比HashMap小多少了