[游戏开发]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<T>
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);
        }