System.Collections.Generic 源码阅读总结

图片 2

ArrayList ,List

ArrayList 和 List 都是不限制长度的集合类型 ,List相比ArrayList
就内部实现而言除了泛型本质没有太大区别。不过为避免装箱拆箱问题,尽可能使用List

集合内部是由数组实现,默认大小是4,但你使用无参构造函数构造实例时,内部数组大小是0,当你加入第一个元素时,才扩容为4,添加元素时,如果发现内置数组大小不够,内置数组大小会扩容为原来的两倍,每一次扩容都会重新开辟一个数组,拷贝旧数组的数据,如果你要给集合添加大量的元素却不为它初始化一个合适容量,频繁的内存开辟和多余的数组拷贝会导致性能的损耗。

所以使用时建议提供合适的容量。

2.优点

1、SortedList
允许通过相关联键或通过索引对值进行访问,可提供更大的灵活性。

2、可根据需要自动增大容量。

SortedSet,SortedDictioanry

SortedSet类似于HashSet,但略有不同的是,SortedSet是有序排列,SortedSet内部实现应该是所有集合中最复杂,是依靠红黑树的原理实现。

SortedDictioanry和Dictionary的区别与HashSet和SortedSet的区别基本一致,因为SortedDictioanry内部本身就是依靠SortedSet实现的,并且SortDictionary内部顺序是以key的顺序为排列的

public SortedDictionary(IDictionary<TKey,TValue> dictionary, IComparer<TKey> comparer) {
          if( dictionary == null) {
              ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary);
          }

          _set = new TreeSet<KeyValuePair<TKey, TValue>>(new KeyValuePairComparer(comparer));

          foreach(KeyValuePair<TKey, TValue> pair in dictionary) {
              _set.Add(pair);
          }            
      }

三:遍历方式:

SortedList

SortedList是支持排序的关联性(键值对 )集合
,内部采用数组实现,所以和List相同的是,初始化时需要提供一个合适的容量,SortedList内部采用哈希算法实现,和Dictionary类似的是,SortedList内部解除哈希冲突的算法是链地址法。

因为在查找的时候利用了二分搜索,所以查找的性能会好一些,时间复杂度是O(log
n)

如果你想要快速查找,又想集合按照key的顺序排列,最后这个集合的操作(添加和移除)比较少的话,就是SortedList了

List<T>和ArrayList的区别
     
List<T>和ArrayList的相同点:添加元素、删除元素、通过索引访问元素方法相同。
  List<T>和ArrayList的不同点:
ArrayList可以添加任意类型元素;List<T>对添加的元素具有类型约束;
ArratList添加时装箱,读取时拆箱;List<T>不需要装箱,拆箱操作;

HashSet

HashSet是一个无序的能够保持唯一性的集合。我们也可以把HashSet看作是Dictionary<TKey,TValue>,只不过TKey和TValue都指向同一个对象。内部实现和Dictionary非常相似。
HashSet非常适合在我们需要保持集合内元素唯一性但又不需要按顺序排列的时候。

2.ArrayList
提供添加、插入或移除某一范围元素的方法。在 Array
中,您只能一次获取或设置一个元素的值。

LinkedList,Stack,Queue

这3个集合我就不多做解释,完全按这几个基础数据结构的原理来实现。不过Stack,Queue内部采用数组实现,所以也要注意初始化时提供一个恰当的容量啊

Pop()       //出栈 

hashtable,Dictionary

hashtable和Dictionary都是哈希表的实现,很多人说Dictionary内部是由hashtable实现的,这是不恰当的。

hashtable的构造需要装载因子,装载因子是0.1 到 1.0 范围内的数字
,是内部存储桶数(count)所占桶数组(buckets)桶数(hashsize)的最大比率
,当桶数大于装载数(loadsize)时,桶数组就会扩容

hashtable内部解除哈希冲突的算法是双重散列法,是开放地址法中最好的方法之一

而不同的是,Dictionary内部解除哈希冲突的算法是链地址法,而且Dictionary的构造不需要装载因子,不受装载因子的限制
,如果Dictionary非常小,查找,插入,删除等操作拥有近乎O(1)的效率

和ArrayList
,List类似的是Dictionary和hashtable内部也是由数组实现的,所以构造时也需要提供合适容量,防止性能的损耗。

但我们需要另外注意的是你提供给构造函数的容量不一定会是初始时内置数组的长度,构造函数内部会选择一个大于等于你所选择容量的素数作为真实的初始容量。

一:ArrayList:

Stack 的主要成员:

1.HashTable大数据量插入数据时需要花费比Dictionary大的多的时间。

Queue对应Queue

1、SortedList定义

System.Collections.SortedList类表示键/值对的集合,这些键值对按键排序并可按照键和索引访问。SortedList
在内部维护两个数组以存储列表中的元素;即,一个数组用于键,另一个数组用于相关联的值。每个元素都是一个可作为
DictionaryEntry.aspx)
对象进行访问的键/值对。键不能为null,但值可以。

Dictionary的几种遍历方式:

一:HashTable:

Count    //元素数     

C#
泛型集合之非泛型集合类与泛型集合类的对应:

泛型集合List<T>
  泛型最重要的应用就是集合操作,使用泛型集合可以提高代码重用性,类型安全和更佳的性能。
  List<T>的用法和ArrayList相似,List<T>有更好的类型安全性,无须拆,装箱。
在泛型定义中,泛型类型参数“<T>”是必须指定的,其中T是定义泛型类时的占位符,其并不是一种类型,仅代表某种可能的类型。在定义时T会被使用的类型代替。泛型集合List<T>中只能有一个参数类型,“<T>”中的T可以对集合中的元素类型进行约束。

Array的容量是固定的 先指定大小
在赋值

5.Array 提供 ArrayList
所不具有的某些灵活性:

Stack对应Stack

2.分离链接散列表是当散列到同一个地址的值存为一个链表中。

 Array arrayList2 = Array.CreateInstance(typeof(string), 6);
             arrayList2.SetValue("a", 0);
             arrayList2.SetValue("b", 1);
             Response.Write(arrayList2.GetValue(1));
public class HashTableTest

    {

        static Hashtable _Hashtable;

        static Dictionary<string, object> _Dictionary;

        static void Main()

        {

            Compare(10);

            Compare(10000);

            Compare(5000000);

            Console.ReadLine();

        }

        public static void Compare(int dataCount)

        {

            Console.WriteLine("-------------------------------------------------n");

            _Hashtable = new Hashtable();

            _Dictionary = new Dictionary<string, object>();

            Stopwatch stopWatch = new Stopwatch();

            //HashTable插入dataCount条数据需要时间

            stopWatch.Start();

            for (int i = 0; i < dataCount; i++)

            {

                _Hashtable.Add("Str" + i.ToString(), "Value");

            }

            stopWatch.Stop();

            Console.WriteLine(" HashTable插入" + dataCount + "条数据需要时间:" + stopWatch.Elapsed);



            //Dictionary插入dataCount条数据需要时间

            stopWatch.Reset();

            stopWatch.Start();

            for (int i = 0; i < dataCount; i++)

            {

                _Dictionary.Add("Str" + i.ToString(), "Value");

            }

            stopWatch.Stop();

            Console.WriteLine(" Dictionary插入" + dataCount + "条数据需要时间:" + stopWatch.Elapsed);



            //Dictionary插入dataCount条数据需要时间

            stopWatch.Reset();

            int si = 0;

            stopWatch.Start();

            for(int i=0;i<_Hashtable.Count;i++)

            {

                si++;

            }

            stopWatch.Stop();

            Console.WriteLine(" HashTable遍历时间:" + stopWatch.Elapsed + " ,遍历采用for方式");



            //Dictionary插入dataCount条数据需要时间

            stopWatch.Reset();

            si = 0;

            stopWatch.Start();

            foreach (var s in _Hashtable)

            {

                si++;

            }

            stopWatch.Stop();

            Console.WriteLine(" HashTable遍历时间:" + stopWatch.Elapsed + " ,遍历采用foreach方式");



            //Dictionary插入dataCount条数据需要时间

            stopWatch.Reset();

            si = 0;

            stopWatch.Start();

            IDictionaryEnumerator _hashEnum = _Hashtable.GetEnumerator();

            while (_hashEnum.MoveNext())

            {

                si++;

            }

            stopWatch.Stop();

            Console.WriteLine(" HashTable遍历时间:" + stopWatch.Elapsed + " ,遍历采用HashTable.GetEnumerator()方式");



            //Dictionary插入dataCount条数据需要时间

            stopWatch.Reset();

            si = 0;

            stopWatch.Start();

            for(int i=0;i<_Dictionary.Count;i++)

            {

                si++;

            }

            stopWatch.Stop();

            Console.WriteLine(" Dictionary遍历时间:" + stopWatch.Elapsed + " ,遍历采用for方式");



            //Dictionary插入dataCount条数据需要时间

            stopWatch.Reset();

            si = 0;

            stopWatch.Start();

            foreach (var s in _Dictionary)

            {

                si++;

            }

            stopWatch.Stop();

            Console.WriteLine(" Dictionary遍历时间:" + stopWatch.Elapsed + " ,遍历采用foreach方式");



            //Dictionary插入dataCount条数据需要时间

            stopWatch.Reset();

            si = 0;

            stopWatch.Start();

            _hashEnum = _Dictionary.GetEnumerator();

            while (_hashEnum.MoveNext())

            {

                si++;

            }

            stopWatch.Stop();

            Console.WriteLine(" Dictionary遍历时间:" + stopWatch.Elapsed + " ,遍历采用Dictionary.GetEnumerator()方式");





            Console.WriteLine("n-------------------------------------------------");

        }

    }

因为HashTable可以通过Hashtable tab =
Hashtable.Synchronized(new Hashtable());获得线程安全的对象。

3.当一个HashTable被占用一大半的时候我们通过计算散列值取得的地址值可能会重复指向同一地址,这就是哈希冲突。

1.HashTable是一种散列表,他内部维护很多对Key-Value键值对,其还有一个类似索引的值叫做散列值(HashCode),它是根据GetHashCode方法对Key通过一定算法获取得到的,所有的查找操作定位操作都是基于散列值来实现找到对应的Key和Value值的。

基于以下代码对Queue 与
Stack进行了性能测试,他们的性能都比数组要高大约2~倍。

Stack:它是一个后进先出的集合(它存储于栈中),后进先出的意思顾名思义,也就是说取数据只能从最后放进去的那个数据开始取。

方法 

Queue:它是一个先进先出的集合(它存储于队列中),先进先出的意思也就是最先放进集合的数据,拿数据的时候从最初放进去的数据开始拿。

1.Dictionary是一种变种的HashTable,它采用一种分离链接散列表的数据结构来解决哈希冲突的问题。

 1:单线程程序中推荐使用 Dictionary, 有泛型优势, 且读取速度较快,
容量利用更充分.
 2:多线程程序中推荐使用 Hashtable, 默认的 Hashtable 允许单线程写入,
多线程读取, 对 Hashtable 进一步调用 Synchronized()
方法可以获得完全线程安全的类型. 而 Dictionary 非线程安全, 必须人为使用
lock 语句进行保护, 效率大减.
 3:Dictionary 有按插入顺序排列数据的特性 (注: 但当调用 Remove()
删除过节点后顺序被打乱), 因此在需要体现顺序的情境中使用 Dictionary
能获得一定方便.

eg:

第五:SortedList

eg:本文将以代码的形式探索HashTable和Dictionary的插入和三种读取方式的效率(for/foreach/GetEnumerator)

Push()       //压栈 

   b.Array 可以具有多个维度,而 ArrayList
始终只是一维的。

图片 1

HashTable的遍历方式:

static void Main(string[] args)
 2         {
 3             Person person1 = new Person();
 4             person1.Age = 34;
 5             person1.Name = "Jacky";
 6             person1.Email = "Jacky@gmail.com";
 7 
 8             Person person2 = new Person();
 9             person2.Age = 23;
10             person2.Name = "Ajay";
11             person2.Email = "Ajay@gmail.com";
12 
13             Person person3 = new Person();
14             person3.Age = 12;
15             person3.Name = "Bill";
16             person3.Email = "Bill@gmail.com";
17 
18             Person person4 = new Person();
19             person4.Age = 23;
20             person4.Name = "Gace";
21             person4.Email = "Gace@gmail.com";
22 
23             Person person5 = new Person();
24             person5.Age = 45;
25             person5.Name = "Jim";
26             person5.Email = "Jim@gmail.com";
27 
28             Hashtable ht = new Hashtable();
29             ht.Add("1", person1);
30             ht.Add("2", person2);
31             ht.Add("3", person3);
32             ht.Add("4", person4);
33             ht.Add("5", person5);
34             Console.WriteLine("请输入你的查询的用户名:");
35             string strName = Console.ReadLine();
36             //第一种方法 key值
37              foreach (string item in ht.Keys)
38             {
39                 Person p = (Person)ht[item];
40                 if (strName == p.Name)
41                 {
42                     Console.WriteLine("查询后的结果是:" + p.Name + "t" + p.Email + "t" + p.Age);
43                 }
44             }
45 
46 
47 
48             //第二种方法 value值
49              foreach (Person item in ht.Values)
50             {
51                 if (item.Name == strName)
52                 {
53                     Console.WriteLine("查询后的结果是:" + item.Name + "t" + item.Email + "t" + item.Age);
54                 }
55 
56             }
57             //第三种方法 key和value值
58              foreach (DictionaryEntry item in ht)
59             {
60                 if (strName == ((Person)item.Value).Name)
61                 {
62                     Console.WriteLine("查询后的结果是:" + ((Person)item.Value).Name + "t" + ((Person)item.Value).Email + "t" + ((Person)item.Value).Age);
63                 }
64             }
65 
66             //第四种方法
67              IDictionaryEnumerator id = ht.GetEnumerator();
68             while (id.MoveNext())
69             {
70              Person p =   (Person)ht[id.Key];
71              if (p.Name == strName)
72              {
73                  Console.WriteLine("查询后的结果是:" + p.Name + "t" + p.Email + "t" + p.Age);
74              }
75             }
76 
77         }

5..当前HashTable中的被占用空间达到一个百分比的时候就将该空间自动扩容,在.net中这个百分比是72%,也叫.net中HashTable的填充因子为0.72。例如有一个HashTable的空间大小是100,当它需要添加第73个值的时候将会扩容此HashTable.

Dequeue() //出列 

Hashtable 和
Dictionary <K, V> 类型

6.这个自动扩容的大小是多少呢?答案是当前空间大小的两倍最接近的素数,例如当前HashTable所占空间为素数71,如果扩容,则扩容大小为素数131.

五:在单线程的时候使用Dictionary更好一些,多线程的时候使用HashTable更好。

List泛型集合:

ArrayList arrayList1 = new ArrayList();
             arrayList1.
             arrayList1.Add("a");
             arrayList1.Add(1);
             arrayList1.Add("b");
             Response.Write(arrayList1[1]);

eg: hashtable

1:Add()向数组中添加一个元素,
2:Remove()删除数组中的一个元素
3:(int i)删除数组中索引值为i的元素
4:Reverse()反转数组的元素
5:Sort()以从小到大的顺序排列数组的元素
6:Clone()复制一个数组

ArrayList对应List

测试结果:
图片 2

属性   Count       //     

eg:
List<T>添加、删除、检索元素的方法和ArrayList相似,明显的特点是不需要像ArrayList那样装箱和拆箱。

You can leave a response, or trackback from your own site.

Leave a Reply

网站地图xml地图