数组

实现

数组在内存中时连续存储的，所以其索引速度非常快，而且赋值和修改元素也比较简单

特性

数据在插入和删除元素时比较麻烦

我们在声明一个数组的时候，必须同时指明数组的长度，数组长度过长会导致内存浪费
数组长度过短，回导致数据溢出的错误

所以在声明数组的时候，我们是必须权衡一个比较完美的数值，c#中提供的ArrayList就完美克服了这些缺点

ArrayList

实现

不定长的，连续分配的,类型不安全,读取快—增删慢，如果是值类型，会有装箱的操作

ArrayList底层是用数组实现的，对于ArrayList而言，实现List接口，底层使用数组保存所有元素，其操作基本上是对数组的操作

ArrayList是Syetem.Colllections下的一个部分，它的大小是按照其中存储的数据进行动态扩充和收缩的
所以我们在声明ArrayList对象的时候，完全不用考虑内存的浪费和指定长度的权衡

特性

ArrayList是很方便进行数值的插入，修改，移除等操作的

可以在ArrayList中可以同时插入不同类型的数据，比如string，char，int等等，因为ArrayList把这些数据当做object来处理的，所以这样是允许的
但是有一个问题，如果我们用ArrayList来处理问题的时候，很可能发生类型不匹配的错误，所以说ArrayList是不安全的
即使我们保证插入数据的时候很小心，但是在使用的时候，我们需要他们都转化成为原来类型来处理
这里就有了拆装箱的操作，可想而知，这样会有巨大的内存消耗，所以有了List

List

实现

读取快—增删慢 底层原理是数组，内存上都是连续摆放；不定长；泛型，保证类型安全，避免装箱拆箱

每个数组是一个节点，节点里面有一个Data和一个指向下一个节点的指针

List类是ArrayList类的泛型等效类，它的大部分用法都与ArrayList相似，因为List类也继承了IList接口。最关键的区别在于，在声明List集合时，我们同时需要为其声明List集合内数据的对象类型。

特性

可变长度

默认声明List长度为0，默认容量为4，在元素数量超过4后按双倍扩容。

1. list在新建表之后的初始长度为0，添加第一个元素之后会生成一个长度为四的表，也就是初始长度
2. 每此添加数据的时候会判断是否超出表长，如果超出表长那么就新建一个list表（这个表的长度是原来表的二倍），然后list表会把之前的表数据复制到新表中
3. 但是之前的表去了哪里呢，在这里我推测，他复制表之后，他直接把指针指向了新的表，并没有管当前的表，所以当前的表会变成内存垃圾等着cg回收

可以设置初始长度如

List<int> lst = new List<int>(1);

也会按0,1,2,4,8的顺序扩容，提高效率

• Capcity与Count都是属性，只是Count是只读不可改而Capcity可读可改
• 我们的扩容实际操作是在Capcity set方法中，设置容量大小时List中的数据被复制到新开辟的泛型数组内，复杂度O(n)
• List的默认容量为4，但是之后在扩容上不是简单的每次都去乘二，其中还有一个int min这个最小值的判断，如下

private void EnsureCapacity(int min) {
            if (_items.Length < min) {
                int newCapacity = _items.Length == 0? _defaultCapacity : _items.Length * 2;
                // Allow the list to grow to maximum possible capacity (~2G elements) before encountering overflow.
                // Note that this check works even when _items.Length overflowed thanks to the (uint) cast
                if ((uint)newCapacity > Array.MaxArrayLength) newCapacity = Array.MaxArrayLength;
                if (newCapacity < min) newCapacity = min;
                Capacity = newCapacity;
            }

Hashtable

实现

HashTable是继承自Dictionary类，实现了Map接口，HashTable的主体还是Entry数组

在.NET Framework中，Hashtable是System.Collections命名空间提供的一个容器，用于处理和表现类似keyvalue的键值对，其中key通常可用来快速查找，同时key是区分大小写；value用于存储对应于key的值。

Hashtable中的数据实际存储在内部的一个数据桶里（bucket结构数组），其和普通的数组一样，容量固定，根据数组索引获取值。

Hashtable中keyvalue键值对均为object类型，所以Hashtable可以支持任何类型的keyvalue键值对.

基本结构

• 一个hashtable有的字段：load fator装填因子（默认为0.72），capacity容量（初始为0），bucket桶的数量（初始为3）。
• 一个hashtable中所有的数据实际上是存储在bucket结构的数组中的，然后可以根据索引（哈希值）去访问桶中的数据。

装入过程

Hashtable ht = new Hashtable()；
ht.Add("a",100);

1. 计算 已有数据的个数/桶的数量的约值，如果该值小于装填因子：
   • 计算“a”的哈希值
   • 得到的哈希值对桶的数量取模得到位置
   • 在桶的该位置，将其key赋值为“a”，value赋值为100。
   • 若哈希出现冲突，则使用开放定址法（线性哈希再散列）的方法 (HashOf(a)+di )% Array.length来寻找下一个位置放入数据。
2. 计算 已有数据的个数/桶的数量的约值，如果该值大于装填因子：
   • 增加桶的数量即扩充数组，扩充到最小两倍当前数组大小的素数（3变为7）
   • 将原桶数组中的所有key全部rehash一遍再放入新的数组中
   • 重复1中的步骤

查找过程

var value = ht["a"]；

1. 计算“a”的哈希值
2. 由该哈希值对桶数组取余得到所在的位置，并比较该位置所在的key是否为“a”，如果是返回其value否则进行开放地址寻找另一个位置，最后返回所在位置的value值

特性

Hashtable查询速度快，而添加速度相对慢，且其添加和查询速度之比相差一个数量等级

Hashtable查询速度近乎是O(1)的，而添加和删除操作是O(n)，因为当容量不够时，要全部rehash一遍拷贝到新的数组。

装填因子（ Load Factor）是什么，hashtable默认的装填因子是多少？

判断是否容量不足的指标是装填因子，当已有数据的个数/桶的数量大于装填因子时表示数量不够需要扩容。默认为0.72是微软官方给它制定的值，因为要考虑：当装填因子过大时，这样hash冲突会非常明显降低性能；当装填因子过小时，桶的数量太多，会造成内存的浪费。

hashtable里的元素是顺序排序的吗？

由计算过程可知是无序的

hashtable内部的数据桶（数组）默认长度多少，其长度为什么只能是素数？

默认长度是3。

是素数的原因是素数的约数只有1和它本身，因而在容量对桶数组作取余操作的时候，得到hash值尽可能是唯一的。

Dictionary

实现

简单来说，dictionary使用两个数组来通过hash存储键值对并且避免冲突的过程。分别是Entries数组和Bucket数组

• 其中entries数组中保存哈希code和键、值，以及一个重要的int型的next的值，就是用这个next值来避免冲突。
• bucket数组中的索引用来保存对应的hashcode在哪个entries数组中去找键值对。

增加元素过程

Dictionary<int,string> dic = new Dictionary<int,string>()；
dic.Add(1,"a")；
dic.Add(2,"b")；
dic.Add(4,"c");
var value = dic[1]；

1. 由于没有给定长度，初始化时，dic的entries数组长度为0，bucket数组长度为0，假如给定为10，则二者长度都为11（为大于10的最大素数）
2. 加入新键值对，两个数组都扩容为3（0~2）（其实是先算1的哈希值，并且判断没有该哈希值或者有该哈希值但是是不同的键才会认定需要增加该键值对，才会扩容），1的哈希值为1，对3取余为1，且bucket[1]为空（0），所以将该键值对和哈希值放在entries[0]中，并将bucket[1]的值设为1，表示第一个entries中存储了哈希值为1的键值对（也就是说bucket数组中的值减一才是对应的entries数组的索引，为什么这么做，因为在没有值的情况下是0，所有bucket数组中的0值毫无意义，所以要从1开始）。
3. 计算2的哈希值为2，并且bucket[2]为空，所以将该键值对放入entries[1]中（entries就是按顺序放入的），并且bucket[2]=2，表示键哈希值为2的键值对存储在第二个entries数组的结构中。
4. 计算2的哈希值为2，并且bucket[2]=2，于是得到key = entries[1].key，得到key = 2，于是抛出异常，键重复。
5. 计算4的哈希值为4，并且对bucket数组长度取余（3）得到1，然而key = bucket[1].key，得到key = 1，得到该键为1不等于4，说明出现了哈希冲突。这里是怎么解决的呢？

首先，该键值对是合法的（没有重复键）那么假如entries数组，也就是entries[2]中放入键值对为2，“c”的结构，同时，注意entry结构中的next值默认是-1，在这里，将entries[2].next = bucket[1]，也就是说，由于我覆盖了bucket[1]的原本的索引也就是entries[0]，因而微软将这里的entries[2]的next值赋值为该索引也就是0；然后bucket[1]的值就改为3，表示哈希值为2的键值对存储在entries数组中的第三个结构中也就是entries[2]

该解决哈希冲突的方法叫做“拉链法”。

6.计算1的哈希值为1，对bucket数组取余为1，得到bucket[1] = 3，进而去找entries[2]，得到键值为4，不等于1，于是找next的值，该值为0，于是在entries[0]中找到键值为1的键值对，其值为“a”，于是返回a

当继续增加元素时，bucket和entries都要扩容，翻倍成为大于自身两倍的最小素数，并且将所有元素全部重新哈希，按照上面的计算方式重新分配bucket数组中的值，entries数组拷贝到一个更大的数组空间中去。

Hashtable与Dictionary

仅仅从resize扩容的角度来看，两者的效率是差不多的，都需要扩容并且rehash，dictionary还需要重建链，但是由于hashtable存在类型转换，所有元素都是object类型，因而一般来说dictionary比hashtable在添加元素上效率差不多，但是对应于查找元素，hashtable只需要一次（或者多次）hash就可以找到，然而dictionary可能还需要遍历链，所以hashtable的查找效率更高。