C#中的数据结构
2020-12-18 03:34
标签：none foreach first ddb sync 索引 散列 影响 延迟 数据结构：集合，线性结构，树形结构，图形结构 集合：纯粹的集合 线性结构：一对一 数组 树形结构：一对多 菜单/文件夹/树形控件 图形结构：多对多，地图/拓扑图/物流 常见数据结构： Array/ArrayList/List/LinkedList/Queue/Stack/HastSet/SortedSet/Hashtable/SortedList/Dictionary/SortedDictionary Array 1、数组（Array） 数组具有以下的特点： 数组属于线性结构，在内存中是连续存放的； 数组的元素类型必须相同； 数组可以通过下标进行访问； 数组的查找速度非常快，新增和删除速度慢； 数组在初始化的时候需要指定数组的长度； 优点：读取快，节约空间 缺点：添加和删除慢，长度不能改变 2、动态数组（ArrayList）（建议使用List 动态数组具有一下特点： ArrayList底层就是一个object类型的数组； ArrayList 会根据存储的数据动态改变长度； ArrayList因为类型是object 所以可以存储不同的数据元素； 添加或删除元素时，会移动之后所有元素的位置，效率底，频繁进行添加或移除操作建议使用LinkedList； ArrayList是非类型安全的 ，使用时会进行拆箱和装箱操作问题，效率底 优点：动态改变长度 缺点：类型不安全，拆装箱 3、泛型List（List List是ArrayList升级版； 泛型List需要在声明的时候指定具体类型； List没有拆装箱操作，List 比ArrayList 效率高 而且类型安全； 优点：类型安全，查找快，长度动态改变 缺点：添加和移动会移动之后的元素，效率底。 链表 4双向链表（LinkedList） 链表在在内存中的空间不是连续的每块空间称为节点，每个节点都存有一个前置和后置指针，分别指向前一节点和后一节点，因此向链表中 添加和删除元素效率高，只需要更改相应节点的指针指向。 链表的查询效率比较底，不能通过下标访问，只能从头开始遍历。 优点：添加和删除效率高 缺点：查询慢 5队列（Queue） Queue是先进先出 Enqueue 入队，Dequeue 出队（移除元素），Peek（不移除）只返回首元素 使用场景：不同的线程捕捉日志放进Queue 中 由统一的线程写日志，避免多线程并发。 6栈（stack） stack 是先进后出 Push入栈，Pop（移除）出栈并返回栈定元素，Peek（不移除）只返回栈顶元素 使用场景：①操作记录为命令，撤销的时候是倒序的；②解析表达式目录树的时候，先产生的数据后使用 7、Dictionary（字典） 创建字典的时候需要指定key和value的数据类型 字典中的key值是唯一的，value的值可以不唯一 可以通过key快速查找对应的value ，速度快，消耗内存 优点：通过key定位值，操作非常快 缺点：耗内存，散列冲突（散列结果一致18，可以让第二次的+1，可能会造成效率的降低，尤其是数据量大的情况下，以前测试过dictionary在3w条左右性能就开始下降的厉害） C#中的数据结构 标签：none foreach first ddb sync 索引 散列 影响 延迟 原文地址：https://www.cnblogs.com/xianchengzhang/p/13914159.html
#region Array
{
//Array：在内存上连续分配的，而且元素类型是一样的
//可以坐标访问 读取快--增删慢，长度不变
Console.WriteLine("***************Array******************");
int[] intArray = new int[3];
intArray[0] = 123;
string[] stringArray = new string[] { "123", "234" };//Array
}
{
//ArrayList 不定长的，连续分配的；
//元素没有类型限制，任何元素都是当成object处理，如果是值类型，会有装箱操作
//读取快--增删慢
Console.WriteLine("***************ArrayList******************");
ArrayList arrayList = new ArrayList();
arrayList.Add("Eleven");
arrayList.Add("Is");
arrayList.Add(32);//add增加长度
//arrayList[4] = 26;//索引复制，不会增加长度
//删除数据
//arrayList.RemoveAt(4);
var value = arrayList[2];
arrayList.RemoveAt(0);
arrayList.Remove("Eleven");
}
{
//List:也是Array，内存上都是连续摆放;不定长；泛型，保证类型安全，避免装箱拆箱
//读取快--增删慢
Console.WriteLine("***************List
#region 链表
{
//LinkedList：泛型的特点;链表，元素不连续分配，每个元素都有记录前后节点
//节点值可以重复
//能不能下标访问？不能，找元素就只能遍历 查找不方便
//增删 就比较方便
Console.WriteLine("***************LinkedList
//读取&增删都快？ 有 hash散列 字典
//key-value，一段连续有限空间放value(开辟的空间比用到的多，hash是用空间换性能)，基于key散列计算得到地址索引，这样读取快
//增删也快，删除时也是计算位置，增加也不影响别人
//肯定会出现2个key(散列冲突)，散列结果一致18，可以让第二次的+1，
//可能会造成效率的降低，尤其是数据量大的情况下，以前测试过dictionary在3w条左右性能就开始下降的厉害
#region key-value
{
//Hashtable key-value 体积可以动态增加 拿着key计算一个地址，然后放入key - value
//object-装箱拆箱 如果不同的key得到相同的地址，第二个在前面地址上 + 1
//查找的时候，如果地址对应数据的key不对，那就 + 1查找。。
//浪费了空间，Hashtable是基于数组实现
//查找个数据 一次定位； 增删 一次定位； 增删查改 都很快
//浪费空间，数据太多，重复定位定位，效率就下去了
Console.WriteLine("***************Hashtable******************");
Hashtable table = new Hashtable();
table.Add("123", "456");
table[234] = 456;
table[234] = 567;
table[32] = 4562;
table[1] = 456;
table["eleven"] = 456;
foreach (DictionaryEntry objDE in table)
{
Console.WriteLine(objDE.Key.ToString());
Console.WriteLine(objDE.Value.ToString());
}
//线程安全
Hashtable.Synchronized(table);//只有一个线程写 多个线程读
}
{
//字典：泛型；key - value，增删查改 都很快；有序的
// 字典不是线程安全 ConcurrentDictionary
Console.WriteLine("***************Dictionary******************");
Dictionaryint, string> dic = new Dictionaryint, string>();
dic.Add(1, "HaHa");
dic.Add(5, "HoHo");
dic.Add(3, "HeHe");
dic.Add(2, "HiHi");
dic.Add(4, "HuHu1");
dic[4] = "HuHu";
dic.Add(4, "HuHu");
foreach (var item in dic)
{
Console.WriteLine($"Key:{item.Key}, Value:{item.Value}");
}
}
{
Console.WriteLine("***************SortedDictionary******************");
SortedDictionaryint, string> dic = new SortedDictionaryint, string>();
dic.Add(1, "HaHa");
dic.Add(5, "HoHo");
dic.Add(3, "HeHe");
dic.Add(2, "HiHi");
dic.Add(4, "HuHu1");
dic[4] = "HuHu";
dic.Add(4, "HuHu");
foreach (var item in dic)
{
Console.WriteLine($"Key:{item.Key}, Value:{item.Value}");
}
}
{
//"a".GetHashCode();
Console.WriteLine("***************SortedList******************");
SortedList sortedList = new SortedList();//IComparer
sortedList.Add("First", "Hello");
sortedList.Add("Second", "World");
sortedList.Add("Third", "!");
sortedList["Third"] = "~~";//
sortedList.Add("Fourth", "!");
sortedList.Add("Fourth", "!");//重复的Key Add会错
sortedList["Fourth"] = "!!!";
var keyList = sortedList.GetKeyList();
var valueList = sortedList.GetValueList();
sortedList.TrimToSize();//用于最小化集合的内存开销
sortedList.Remove("Third");
sortedList.RemoveAt(0);
sortedList.Clear();
}
#endregion