Unity基础之数据结构

Unity中常用的数据结构学习与总结

看了c#提供的数据结构的源码后,也清晰了各个数据结构的优缺点,也是面试或工作都必须要掌握的东西,希望我的总结能帮到你们。

常用的数据结构

Array
  • 特点
    • Array内部是一块连续的地址,可以是多维数组
    • 声明时必须先要声明类型
    • 没有自动扩容,必须重新初始化(这点很重要)
    • 在大量数据上时,增删速度慢,因为会产生排序问题
  • 总结
    • Array的作用是分配一块连续的地址,Array是所有的容器设计的基础,字典的内部或List的内部都是依靠他来存储的
//初始化
int[] intArray = new int[5];
//赋值
intArray[0] = 1;
intArray[1] = 1;
intArray[2] = 1;
intArray[3] = 1;
intArray[4] = 1;
//会报错超出索引,且Array不会自动扩容
intArray[5] = 1;
//会报错,存放的类型也必须一致
intArray[6] = "文字";
ArrayList
  • 特点
    • 他是基于Array实现的容器
    • 相对于Array,ArrayList多了自动扩容的功能,以及一些增删改查的方法
    • 内部Array存放的是Object集合,所以是非类型安全容器,会引发拆箱装箱的问题
    • 当容器满时,再进行添加时会将容器扩容两倍,默认的大小为4
  • 总结
    • 可以简单的说成是Array的加强版,但是ArrayList不是一个泛型实现,他会有类型不安全的问题,会导致拆箱装箱的情况
//初始化化
ArrayList arrayList = new ArrayList(0); //不指定大小的初始化,会构造一个空的容器
ArrayList arrayList2 = new ArrayList(1); //指定大小的初始化
ArrayList arrayList3 = new ArrayList(arrayList2); //传入一个继承了ICollection 接口的容器,会将该容器的元素全部复制
//自动扩容:将当前容器乘于二
arrayList2.Add(1); //1
arrayList2.Add(1); //2
arrayList2.Add(1); //4
arrayList2.Add(1); //4
arrayList2.Add(1); //8
Console.WriteLine("扩容后的大小:" + arrayList2.Capacity);
List
  • 特点
    • 他是基于ArrayList实现的泛型容器
    • 它具有ArrayList的功能,但是他是类型安全的容器,不会引发拆箱装箱的情况
  • 总结
    • 与ArrayList一样,不过是一个泛型实现的容器,可以看ArrayList
//List是ArrayList的泛型类,声明时需要指定类型,没有拆箱装箱,具有安全类型
List<int> a = new List<int>();

//使用IReadOnlyCollection来实例化List那么只能通过foreach来遍历 因为他继承实现了IEnumerable
IReadOnlyCollection<int> collectionList = new List<int>() {
      1, 2, 3 };
IEnumerator<int> ienum = collectionList.GetEnumerator();
foreach (int item in collectionList)
{
     
    Console.WriteLine(item);
}

//IReadOnlyList 可以通过索引来获取对应元素
IReadOnlyList<int> readList = new List<int>() {
      1,2,3};
int readEle = readList[1];
Console.WriteLine(readEle);
HashTable
  • 特点

    • 他是一个存储Key value的容器,实际内部存储的元素是一个包含key value heahcode的结构体
    • 存储的对象为Object类型,和ArrayList一样是类型不安全的容器
    • 每存入一个元素就会获取hashcode以及一个Incr的变量,当发生hash冲突时会将桶的位置根据Incr进行重新计算,HashTable采用的是双重散列法来解决冲突,
  • 总结

    • 在类型确定的情况下使用字典会比HashTable更好。在性能方面字典会优于HashTable
//双重散列法的函数
private uint InitHash(Object key, int hashsize, out uint seed, out uint incr) {
     
       //获取code
       uint hashcode = (uint) GetHash(key) & 0x7FFFFFFF;
       seed = (uint) hashcode;
   	   //当hash冲突时会使用incr来重新计算插入的位置
       incr = (uint)(1 + ((seed * HashPrime) % ((uint)hashsize - 1)));
       return hashcode;
}
Dictionary
  • 特点
    • 与HashTable相同,他是一个存储Key value的容器,实际内部存储的元素是一个包含key value heahcode的结构体,但是多了一个Next指针,这个指针用于指向下一个对象
    • 字典是HashTable的泛型实现,不同的是,在解决hash冲突时,字典采用的是拉链法,而Next指针就是用来指向冲突的对象,当冲突的对象会被加入到该桶(Bucket)的链表的中
    • 通过取余的方式确定桶的位置,以及桶的数量,在增删改查时通过确定桶的位置来遍历这个单链表,这样能减少遍历的数量
    • 字典内部为了防止删除莫个元素导致Array排序问题,使用了Freecount 和 FreeList来判断是否有被删除或者未使用的索引,这样在Remove一个元素时,会使用FreeList来等待后面新加入的元素
  • 总结
    • 虽然冲突的元素是放入到链表中,但实际上所有的元素都是存储在Array中,只不过通过Next指针来指向下一个元素
//存入的key value 会多出一个hashcode 以及 next指针
//实际存储在字典中的元素
private struct Entry {
     
  public int hashCode;    // Lower 31 bits of hash code, -1 if unused
  public int next;        // Index of next entry, -1 if last
  public TKey key;           // Key of entry
  public TValue value;         // Value of entry
 }
Queue
  • 特点
    • 先进先出;先加入到队列的元素会先被取出来
    • 队列内部存储实际还是一个Array,只不过在增删时只能处理底部的元素(先加入的元素)
    • 队列在使用Dequeue时为了防止Array排序的问题,使用取余的方式进行存储,所以你以为我们新增的元素会是一条龙一样一直排序下去,实际上后面新增的元素可能会在Array的最前面
  • 总结
    • Queue是基于Array实现的容器,只能对头部进行处理的容器。
//将队列中的元素复制到list
Queue<int> intQue = new Queue<int>();
    intQue.Enqueue(1);
    intQue.Enqueue(2);
    intQue.Enqueue(3);
    int[] intsList = new int[3];
    intQue.CopyTo(intsList, 0);
    foreach (var item in intsList)
    {
     
        Console.WriteLine("从队列中Copy来的元素:" + item);
    }
Stack
  • 特点
    • 与Queue相反先进后出;先加入到栈的元素会后被取出来
    • stack内部存储实际还是一个Array,只不过在增删时只能处理顶部的元素(后加入的元素)
    • 队列在使用Dequeue时为了防止Array排序的问题,使用取余的方式进行存储,所以你以为我们新增的元素会是一条龙一样一直排序下去,实际上后面新增的元素可能会在Array的最前面
  • 总结
    • Stack是基于Array实现的容器,只能对最后加入的元素进行处理的容器。
//1.使用BCL中的Stack
Stack<char> stack = new Stack<char>();
stack.Push('a');//添加数据//先添加的为栈底
stack.Push('b');//添加数据
stack.Push('c');//添加数据//后添加的为栈顶
Console.WriteLine("Count获取stack中的数据个数:"+stack.Count);
char pop = stack.Pop();//取得栈顶的数据并返回
Console.WriteLine("Pop删除并取得栈顶的数据"+pop);
char peek = stack.Peek();
Console.WriteLine("Peek取得栈顶数据"+peek);
LinkedList
  • 特点
    • c#提供的链表是一个双头链表
    • 链表在添加或删除元素时不会发生排序等情况,但是查询元素时不能通过下标查询,只能遍历所有元素
  • 总结
    • 如果存在经常删除或增加的情况使用链表,经常查询使用其他容器会更有效率
LinkedList<int> a = new LinkedList<int>();
//在链表的最后一个新增一个节点
a.AddLast(1);
//在链表的最前方新增一个节点
a.AddFirst(2);
//在指定的节点的前面新增一个节点
a.AddAfter(a.Find(1), 3);
//在指定的节点的后面新增一个节点
a.AddBefore(a.Find(2), 4);
BitArray
  • 特点
    • 一个用来存储位的容器
  • 总结
    • 使用的不多,内部存储的实际是true 或 false 来表示1 或 0
//字节的存储范围为0-255
byte[] bt = {
      60 } ;
BitArray bitArray;
bitArray = new BitArray(bt);
foreach (var item in bitArray)
{
     
   Console.WriteLine(item);
   //输出为 False False True True True True False False  00111100
}

比较重要的类

  1. IEnumerable
    要想使用Foreach来遍历集合必须需要自己继承IEnumerable接口实现GetEnumerator方法
    class Enginner 
    {
     
        public String Name {
      get; set; }
        public int Age {
      get; set; }

        public Enginner(string name, int age) 
        {
     
            this.Name = name;
            this.Age = age;
        }
    }
	
    class DepartMent :IEnumerable
    {
     
        Enginner[] enginners;
        public DepartMent() 
        {
     
            enginners = new Enginner[3];
            enginners[0] = new Enginner("Alan", 23);
            enginners[1] = new Enginner("Kino", 24);
            enginners[2] = new Enginner("Bruce", 28);
        }

        public IEnumerator GetEnumerator()
        {
     
            return enginners.GetEnumerator();
        }
    }

//----自定义一个可遍历的集合类----
        Console.WriteLine("----自定义一个可遍历的集合类----");
        DepartMent departMent = new DepartMent();
        foreach (Enginner item in departMent)
        {
     
            Console.WriteLine(item.Age + " " + item.Name);
        }

你可能感兴趣的