精华内容
下载资源
问答
  • hashSet,hashtable,hashMap 都是基于散列函数, 时间复杂度 O(1) ,但是如果太差的话是O(n); TreeSet==>O(log(n))==> 基于树的搜索,只需要搜索一半即可 O⑴的原因是离散后,下标对应关键字 hash就是...

    hashSet,hashtable,hashMap 都是基于散列函数, 时间复杂度 O(1) ,但是如果太差的话是O(n);

    TreeSet==>O(log(n))==> 基于树的搜索,只需要搜索一半即可

    O⑴的原因是离散后,下标对应关键字
    

    hash就是散列,甚至再散列。但是我一直对hash表的时间复杂度有个疑问。一个需要存储的字符串,通过hash函数散列到一个相对较短的索引,使得存取速度加快。但为什么存取的时间复杂度能达到常量级O(1)呢?? 查找时搜索索引不需要费时间吗?为什么不是O(n)呢? n是hash表的长度,

    如果对Hashtable的构造有很深的理解的话,就知道了,Hashtable 其实是综合了数组和链表的优点,当Hashtable对数值进行搜索的时候,首先用该数值与Hashtable的长度做了取模的操作,得到的数字直接作为hashtable中entry数组的index,因为hashtable是由entry数组组成的,因此,可以直接定位到指定的位置,不需要搜索,当然,这里还有个问题,每个entry其实是链表,如果entry有很多值的话,还是需要挨个遍历的,因此可以这样讲Hashtable的时间复杂度最好是O(1)但是最差是 O(n) 最差的时候也就是hashtable中所有的值的hash值都一样,都分配在一个entry里面,当然这个概率跟中1亿彩票的概率相差不大。

    在看起来就是对Entry链表的循环的时间复杂度影响最大,链表查找的时间复杂度为O(n),与链表长度有关。我们要保证那个链表长度为1,才可以说时间复杂度能满足O(1)。但这么说来只有那个hash算法尽量减少冲突,才能使链表长度尽可能短,理想状态为1。因此可以得出结论:HashMap的查找时间复杂度只有在最理想的情况下才会为O(1),最差是O(n),而要保证这个理想状态不是我们开发者控制的。

    常用数据结构的时间复杂度

    转自
    http://www.cnblogs.com/aspirant/p/8902285.html
    http://www.cnblogs.com/aspirant/p/8908399.html
    http://www.cnblogs.com/aspirant/p/8906018.html

    展开全文
  • 阿里的人问 数组的时间复杂度是多少,链表的是多少,hashmap的时间复杂度是多少。。。。。 后来才知道,时间复杂度是要区分 增删改查的。。。。主要看查询的时间复杂度; 1、数组 查询的时间复杂度 O(n) 2、链表 ...

    hashmap的扩容因子是0.75 原因 参考:HashMap默认加载因子为什么选择0.75?(阿里)

    阿里的人问 数组的时间复杂度是多少,链表的是多少,hashmap的时间复杂度是多少。。。。。

    后来才知道,时间复杂度是要区分 增删改查的。。。。主要看查询的时间复杂度;

    1、数组 查询的时间复杂度 O(n)

    2、链表 查询的时间复杂度 O(n)

    3、hashmap  查询的时间复杂度 O(1)

    数组 查询的时间复杂度 O(n)

    建议看一下下面的博客:

     

    hashSet,hashtable,hashMap 都是基于散列函数, 时间复杂度 O(1) 但是如果太差的话是O(n)

    TreeSet==>O(log(n))==> 基于树的搜索,只需要搜索一半即可

     

    O⑴的原因是离散后,下标对应关键字
    hash就是散列,甚至再散列。但是我一直对hash表的时间复杂度有个疑问。一个需要存储的字符串,通过hash函数散列到一个相对较短的索引,使得存取速度加快。但为什么存取的时间复杂度能达到常量级O(1)呢?? 查找时搜索索引不需要费时间吗?为什么不是O(n)呢? n是hash表的长度,

    如果对Hashtable的构造有很深的理解的话,就知道了,Hashtable 其实是综合了数组和链表的优点,当Hashtable对数值进行搜索的时候,首先用该数值与Hashtable的长度做了取模的操作,得到的数字直接作为hashtable中entry数组的index,因为hashtable是由entry数组组成的,因此,可以直接定位到指定的位置,不需要搜索,当然,这里还有个问题,每个entry其实是链表,如果entry有很多值的话,还是需要挨个遍历的,因此可以这样讲Hashtable的时间复杂度最好是O(1)但是最差是 O(n) 最差的时候也就是hashtable中所有的值的hash值都一样,都分配在一个entry里面,当然这个概率跟中1亿彩票的概率相差不大。

    如果还不理解可以参考我写的专门的博客:

    关于HashMap的:HashMap的实现原理--链表散列

    关于Hashtable的:Hashtable数据存储结构-遍历规则,Hash类型的复杂度为啥都是O(1)-源码分析 

    在看起来就是对Entry链表的循环的时间复杂度影响最大,链表查找的时间复杂度为O(n),与链表长度有关。我们要保证那个链表长度为1,才可以说时间复杂度能满足O(1)。但这么说来只有那个hash算法尽量减少冲突,才能使链表长度尽可能短,理想状态为1。因此可以得出结论:HashMap的查找时间复杂度只有在最理想的情况下才会为O(1),最差是O(n),而要保证这个理想状态不是我们开发者控制的。

    ======================================================================开始=======================================================================================

    常用数据结构的时间复杂度

    常用数据结构的时间复杂度
    Data Structure新增查询/Find删除/DeleteGetByIndex
       数组  Array (T[])O(n)O(n)O(n)O(1)
       链表 Linked list (LinkedList<T>)O(1)O(n)O(n)O(n)
    Resizable array list (List<T>)O(1)O(n)O(n)O(1)
    Stack (Stack<T>)O(1)-O(1)-
    Queue (Queue<T>)O(1)-O(1)-
    Hash table (Dictionary<K,T>)O(1)O(1)O(1)-
    Tree-based dictionary(SortedDictionary<K,T>)O(log n)O(log n)O(log n)-
    Hash table based set (HashSet<T>)O(1)O(1)O(1)-
    Tree based set (SortedSet<T>)O(log n)O(log n)O(log n)-

     

     

     

     

     

     

     

     

     

     

    如何选择数据结构

    Array (T[])

    • 当元素的数量是固定的,并且需要使用下标时。

    Linked list (LinkedList<T>)

    • 当元素需要能够在列表的两端添加时。否则使用 List<T>。

    Resizable array list (List<T>)

    • 当元素的数量不是固定的,并且需要使用下标时。

    Stack (Stack<T>)

    • 当需要实现 LIFO(Last In First Out)时。

    Queue (Queue<T>)

    • 当需要实现 FIFO(First In First Out)时。

    Hash table (Dictionary<K,T>)

    • 当需要使用键值对(Key-Value)来快速添加和查找,并且元素没有特定的顺序时。

    Tree-based dictionary (SortedDictionary<K,T>)

    • 当需要使用价值对(Key-Value)来快速添加和查找,并且元素根据 Key 来排序时。

    Hash table based set (HashSet<T>)

    • 当需要保存一组唯一的值,并且元素没有特定顺序时。

    Tree based set (SortedSet<T>)

    • 当需要保存一组唯一的值,并且元素需要排序时。

    Array

    在计算机程序设计中,数组(Array)是最简单的而且应用最广泛的数据结构之一。在任何编程语言中,数组都有一些共性:

    • 数组中的内容是使用连续的内存(Contiguous Memory)来存储的。
    • 数组中的所有元素必须是相同的类型,或者类型的衍生类型。因此数组又被认为是同质数据结构(Homegeneous Data Structures)。
    • 数组的元素可以直接被访问。比如你需要访问数组的第 i 个元素,则可以直接使用 arrayName[i] 来访问。

    对于数组的常规操作包括:

    • 分配空间(Allocation)
    • 数据访问(Accessing)

    在 C# 中,可以通过如下的方式声明数组变量。

    int allocationSize = 10;
    bool[] booleanArray = new bool[allocationSize];
    FileInfo[] fileInfoArray = new FileInfo[allocationSize];

     

    上面的代码将在 CLR 托管堆中分配一块连续的内存空间,用以容纳数量为 allocationSize ,类型为 arrayType 的数组元素。如果 arrayType 为值类型,则将会有 allocationSize 个未封箱(unboxed)的 arrayType 值被创建。如果 arrayType 为引用类型,则将会有 allocationSize 个 arrayType 类型的引用被创建。

     

    如果我们为 FileInfo[] 数组中的一些位置赋上值,则引用关系为下图所示。

     

    .NET 中的数组都支持对元素的直接读写操作。语法如下:

    // 读数组元素
    bool b = booleanArray[7];
     
    // 写数组元素
    booleanArray[0] = false;

     

    访问一个数组元素的时间复杂度为 O(1),因此对数组的访问时间是恒定的。也就是说,与数组中包含的元素数量没有直接关系,访问一个元素的时间是相同的。

    ArrayList

    由于数组是固定长度的,并且数组中只能存储同一种类型或类型的衍生类型。这在使用中会受到一些限制。.NET 提供了一种数据结构 ArrayList 来解决这些问题。

    ArrayList countDown = new ArrayList();
    countDown.Add(3);
    countDown.Add(2);
    countDown.Add(1);
    countDown.Add("blast off!");
    countDown.Add(new ArrayList());

     

     

    ArrayList 是长度可变的数组,并且它可以存储不同类型的元素。

     

    但这些灵活性是以牺牲性能为代价的。在上面 Array 的描述中,我们知道 Array 在存储值类型时是采用未装箱(unboxed)的方式。由于 ArrayList 的 Add 方法接受 object 类型的参数,导致如果添加值类型的值会发生装箱(boxing)操作。这在频繁读写 ArrayList 时会产生额外的开销,导致性能下降。

    List<T>

    当 .NET 中引入泛型功能后,上面 ArrayList 所带来的性能代价可以使用泛型来消除。.NET 提供了新的数组类型 List<T>。

    泛型允许开发人员在创建数据结构时推迟数据类型的选择,直到使用时才确定选择哪种类型。泛型(Generics)的主要优点包括:

    • 类型安全(Type Safety):使用泛型定义的类型,在使用时仅能使用指定的类型或类型的衍生类型。
    • 性能(Performance):泛型移除了运行时类型检测,消除了装箱和拆箱的开销。
    • 可重用(Reusability):泛型打破了数据结构与存储数据类型之间的紧耦合。这提高了数据结构的可重用性。

    List<T> 等同于同质的一维数组(Homogeneous self-redimensioning array)。它像 Array 一样可以快速的读取元素,还可以保持长度可变的灵活性。

    // 创建 int 类型列表
    List<int> myFavoriteIntegers = new List<int>();
     
    // 创建 string 类型列表
    List<string> friendsNames = new List<string>();

     

    List<T> 内部同样使用 Array 来实现,但它隐藏了这些实现的复杂性。当创建 List<T> 时无需指定初始长度,当添加元素到 List<T> 中时,也无需关心数组大小的调整(resize)问题。

     
    List<int> powersOf2 = new List<int>();
     
      powersOf2.Add(1);
      powersOf2.Add(2);
     
      powersOf2[1] = 10;
     
      int sum = powersOf2[1] + powersOf2[2];

     

    List<T> 的渐进运行时(Asymptotic Running Time)复杂度与 Array 是相同的。

    LinkedList<T>

    在链表(Linked List)中,每一个元素都指向下一个元素,以此来形成了一个链(chain)。

     

    向链表中插入一个新的节点的渐进时间取决于链表是否是有序的。如果链表不需要保持顺序,则插入操作就是常量时间O(1),可以在链表的头部或尾部添加新的节点。而如果需要保持链表的顺序结构,则需要查找到新节点被插入的位置,这使得需要从链表的头部 head 开始逐个遍历,结果就是操作变成了O(n)。下图展示了插入节点的示例。

     

    链表与数组的不同之处在于,数组的中的内容在内存中时连续排列的,可以通过下标来访问,而链表中内容的顺序则是由各对象的指针所决定,这就决定了其内容的排列不一定是连续的,所以不能通过下标来访问。如果需要更快速的查找操作,使用数组可能是更好的选择。

    使用链表的最主要的优势就是,向链表中插入或删除节点无需调整结构的容量。而相反,对于数组来说容量始终是固定的,如果需要存放更多的数据,则需要调整数组的容量,这就会发生新建数组、数据拷贝等一系列复杂且影响效率的操作。即使是 List<T> 类,虽然其隐藏了容量调整的复杂性,但仍然难逃性能损耗的惩罚。

    链表的另一个优点就是特别适合以排序的顺序动态的添加新元素。如果要在数组的中间的某个位置添加新元素,不仅要移动所有其余的元素,甚至还有可能需要重新调整容量。

    所以总结来说,数组适合数据的数量是有上限的情况,而链表适合元素数量不固定的情况。

    在 .NET 中已经内置了 LinkedList<T> 类,该类实现了双向链表(doubly-linked list)功能,也就是节点同时持有其左右节点的引用。而对于删除操作,如果使用 Remove(T),则运算复杂度为 O(n),其中 n 为链表的长度。而如果使用 Remove(LinkedListNode<T>), 则运算复杂度为 O(1)。

    Queue<T>

    当我们需要使用先进先出顺序(FIFO)的数据结构时,.NET 为我们提供了 Queue<T>。Queue<T> 类提供了 Enqueue 和 Dequeue 方法来实现对 Queue<T> 的存取。

    Queue<T> 内部建立了一个存放 T 对象的环形数组,并通过 head 和 tail 变量来指向该数组的头和尾。

     

    默认情况下,Queue<T> 的初始化容量是 32,也可以通过构造函数指定容量。

    Enqueue 方法会判断 Queue<T> 中是否有足够容量存放新元素。如果有,则直接添加元素,并使索引 tail 递增。在这里的 tail 使用求模操作以保证 tail 不会超过数组长度。如果容量不够,则 Queue<T> 根据特定的增长因子扩充数组容量。

    默认情况下,增长因子(growth factor)的值为 2.0,所以内部数组的长度会增加一倍。也可以通过构造函数中指定增长因子。Queue<T> 的容量也可以通过 TrimExcess 方法来减少。

    Dequeue 方法根据 head 索引返回当前元素,之后将 head 索引指向 null,再递增 head 的值。

    Stack<T>

    当需要使用后进先出顺序(LIFO)的数据结构时,.NET 为我们提供了 Stack<T>。Stack<T> 类提供了 Push 和 Pop 方法来实现对 Stack<T> 的存取。

    Stack<T> 中存储的元素可以通过一个垂直的集合来形象的表示。当新的元素压入栈中(Push)时,新元素被放到所有其他元素的顶端。当需要弹出栈(Pop)时,元素则被从顶端移除。

     

    Stack<T> 的默认容量是 10。和 Queue<T> 类似,Stack<T> 的初始容量也可以在构造函数中指定。Stack<T> 的容量可以根据实际的使用自动的扩展,并且可以通过 TrimExcess 方法来减少容量。

    如果 Stack<T> 中元素的数量 Count 小于其容量,则 Push 操作的复杂度为 O(1)。如果容量需要被扩展,则 Push 操作的复杂度变为 O(n)。Pop 操作的复杂度始终为 O(1)。

    Hashtable

    现在我们要使用员工的社保号作为唯一标识进行存储。社保号的格式为 DDD-DD-DDDD(D 的范围为数字 0-9)。

    如果使用 Array 存储员工信息,要查询社保号为 111-22-3333 的员工,则将会尝试遍历数组的所有选择,即执行复杂度为 O(n) 的查询操作。好一些的办法是将社保号排序,以使查询复杂度降低到 O(log(n))。但理想情况下,我们更希望查询复杂度为 O(1)。

    一种方案是建立一个大数组,范围从 000-00-0000 到 999-99-9999 。

     

    这种方案的缺点是浪费空间。如果我们仅需要存储 1000 个员工的信息,那么仅利用了 0.0001% 的空间。

    第二种方案就是用哈希函数(Hash Function)压缩序列。

    我们选择使用社保号的后四位作为索引,以减少区间的跨度。这样范围将从 0000 到 9999。

     

    在数学上,将这种从 9 位数转换为 4 位数的方式称为哈希转换(Hashing)。可以将一个数组的索引空间(indexers space)压缩至相应的哈希表(Hash Table)。

    在上面的例子中,哈希函数的输入为 9 位数的社保号,输出结果为后 4 位。

    H(x) = last four digits of x

     

    上图中也说明在哈希函数计算中常见的一种行为:哈希冲突(Hash Collisions)。即有可能两个社保号的后 4 位均为 0000。

    当要添加新元素到 Hashtable 中时,哈希冲突是导致操作被破坏的一个因素。如果没有冲突发生,则元素被成功插入。如果发生了冲突,则需要判断冲突的原因。因此,哈希冲突提高了操作的代价,Hashtable 的设计目标就是要尽可能减低冲突的发生。

    避免哈希冲突的一个方法就是选择合适的哈希函数。哈希函数中的冲突发生的几率与数据的分布有关。例如,如果社保号的后 4 位是随即分布的,则使用后 4 位数字比较合适。但如果后 4 位是以员工的出生年份来分配的,则显然出生年份不是均匀分布的,则选择后 4 位会造成大量的冲突。

    我们将选择合适的哈希函数的方法称为冲突避免机制(Collision Avoidance)。

    在处理冲突时,有很多策略可以实施,这些策略称为冲突解决机制(Collision Resolution)。其中一种方法就是将要插入的元素放到另外一个块空间中,因为相同的哈希位置已经被占用。

    例如,最简单的一种实现就是线性挖掘(Linear Probing),步骤如下:

    1. 当插入新的元素时,使用哈希函数在哈希表中定位元素位置;
    2. 检查哈希表中该位置是否已经存在元素。如果该位置内容为空,则插入并返回,否则转向步骤 3。
    3. 如果该位置为 i,则检查 i+1 是否为空,如果已被占用,则检查 i+2,依此类推,直到找到一个内容为空的位置。

    现在如果我们要将五个员工的信息插入到哈希表中:

    Alice (333-33-1234)
    Bob (444-44-1234)
    Cal (555-55-1237)
    Danny (000-00-1235)
    Edward (111-00-1235)

     

    则插入后的哈希表可能如下:

     

    元素的插入过程:

    Alice 的社保号被哈希为 1234,因此存放在位置 1234。
    Bob 的社保号被哈希为 1234,但由于位置 1234 处已经存放 Alice 的信息,则检查下一个位置 1235,1235 为空,则 Bob 的信息就被放到 1235。
    Cal 的社保号被哈希为 1237,1237 位置为空,所以 Cal 就放到 1237 处。
    Danny 的社保号被哈希为 1235,1235 已被占用,则检查 1236 位置是否为空,1236 为空,所以 Danny 就被放到 1236。
    Edward 的社保号被哈希为 1235,1235 已被占用,检查1236,也被占用,再检查1237,直到检查到 1238时,该位置为空,于是 Edward 被放到了1238 位置。

     

    线性挖掘(Linear Probing)方式虽然简单,但并不是解决冲突的最好的策略,因为它会导致同类哈希的聚集。这导致搜索哈希表时,冲突依然存在。例如上面例子中的哈希表,如果我们要访问 Edward 的信息,因为 Edward 的社保号 111-00-1235 哈希为 1235,然而我们在 1235 位置找到的是 Bob,所以再搜索 1236,找到的却是 Danny,以此类推直到找到 Edward。

    一种改进的方式为二次挖掘(Quadratic Probing),即每次检查位置空间的步长为平方倍数。也就是说,如果位置 s 被占用,则首先检查 s + 12 处,然后检查s – 12,s + 22,s – 22,s + 32 依此类推,而不是象线性挖掘那样以 s + 1,s + 2 … 方式增长。尽管如此,二次挖掘同样也会导致同类哈希聚集问题。

    .NET 中的 Hashtable 的实现,要求添加元素时不仅要提供元素(Item),还要为该元素提供一个键(Key)。例如,Key 为员工社保号,Item 为员工信息对象。可以通过 Key 作为索引来查找 Item。

    Hashtable employees = new Hashtable();
     
          // Add some values to the Hashtable, indexed by a string key
          employees.Add("111-22-3333", "Scott");
          employees.Add("222-33-4444", "Sam");
          employees.Add("333-44-55555", "Jisun");
     
          // Access a particular key
          if (employees.ContainsKey("111-22-3333"))
          {
            string empName = (string)employees["111-22-3333"];
            Console.WriteLine("Employee 111-22-3333's name is: "  + empName);
          }
          else
            Console.WriteLine("Employee 111-22-3333 is not in the hash table...");

     

    Hashtable 类中的哈希函数比前面介绍的社保号的实现要更为复杂。哈希函数必须返回一个序数(Ordinal Value)。对于社保号的例子,通过截取后四位就可以实现。但实际上 Hashtable 类可以接受任意类型的值作为 Key,这都要归功于 GetHashCode 方法,一个定义在 System.Object 中的方法。GetHashCode 的默认实现将返回一个唯一的整数,并且保证在对象的生命周期内保持不变。

    Hashtable 类中的哈希函数定义如下:

    H(key) = [GetHash(key) + 1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1))] % hashsize

     

     

    这里的 GetHash(key) 默认是调用 key 的 GetHashCode 方法以获取返回的哈希值。hashsize 指的是哈希表的长度。因为要进行求模,所以最后的结果 H(key) 的范围在 0 至 hashsize – 1 之间。

    当在哈希表中添加或获取一个元素时,会发生哈希冲突。前面我们简单地介绍了两种冲突解决策略:

    线性挖掘(Linear Probing)
    二次挖掘(Quadratic Probing)

     

    在 Hashtable 类中则使用的是一种完全不同的技术,称为二度哈希(rehashing)(有些资料中也将其称为双精度哈希(double hashing))。

    二度哈希的工作原理如下:

    有一个包含一组哈希函数 H1…Hn 的集合。当需要从哈希表中添加或获取元素时,首先使用哈希函数 H1。如果导致冲突,则尝试使用 H2,以此类推,直到 Hn。所有的哈希函数都与 H1 十分相似,不同的是它们选用的乘法因子(multiplicative factor)。

    通常,哈希函数 Hk 的定义如下:

    Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1)))] % hashsize

     

     

    当使用二度哈希时,重要的是在执行了 hashsize 次挖掘后,哈希表中的每一个位置都有且只有一次被访问到。也就是说,对于给定的 key,对哈希表中的同一位置不会同时使用 Hi 和 Hj。在 Hashtable 类中使用二度哈希公式,其始终保持 (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1)) 与 hashsize 互为素数(两数互为素数表示两者没有共同的质因子)。

    二度哈希较前面介绍的线性挖掘(Linear Probing)和二次挖掘(Quadratic Probing)提供了更好的避免冲突的策略。

    Hashtable 类中包含一个私有成员变量 loadFactor,loadFactor 指定了哈希表中元素数量与位置(slot)数量之间的最大比例。例如:如果 loadFactor 等于 0.5,则说明哈希表中只有一半的空间存放了元素值,其余一半都为空。

    哈希表的构造函数允许用户指定 loadFactor 值,定义范围为 0.1 到 1.0。然而,不管你提供的值是多少,范围都不会超过 72%。即使你传递的值为 1.0,Hashtable 类的 loadFactor 值还是 0.72。微软认为loadFactor 的最佳值为 0.72,这平衡了速度与空间。因此虽然默认的 loadFactor 为 1.0,但系统内部却自动地将其改变为 0.72。所以,建议你使用缺省值1.0(但实际

    // Add some employees
    employeeData.Add(455110189) = new Employee("Scott Mitchell");
    employeeData.Add(455110191) = new Employee("Jisun Lee");
     
    // See if employee with SSN 123-45-6789 works here
    if (employeeData.ContainsKey(123456789))

     

    上是 0.72)。

    向 Hashtable 中添加新元素时,需要检查以保证元素与空间大小的比例不会超过最大比例。如果超过了,哈希表空间将被扩充。步骤如下:

    • 哈希表的位置空间几乎被翻倍。准确地说,位置空间值从当前的素数值增加到下一个最大的素数值。
    • 因为二度哈希时,哈希表中的所有元素值将依赖于哈希表的位置空间值,所以表中所有值也需要重新二度哈希。

    由此看出,对哈希表的扩充将是以性能损耗为代价。因此,我们应该预先估计哈希表中最有可能容纳的元素数量,在初始化哈希表时给予合适的值进行构造,以避免不必要的扩充。

    Dictionary<K,T>

    Hashtable 类是一个类型松耦合的数据结构,开发人员可以指定任意的类型作为 Key 或 Item。当 .NET 引入泛型支持后,类型安全的 Dictionary<K,T> 类出现。Dictionary<K,T> 使用强类型来限制 Key 和 Item,当创建 Dictionary<K,T> 实例时,必须指定 Key 和 Item 的类型。

     
    Dictionary<keyType, valueType> variableName = new Dictionary<keyType, valueType>();

     



    如果继续使用上面描述的社保号和员工的示例,我们可以创建一个 Dictionary<K,T> 的实例:

    Dictionary<int, Employee> employeeData = new Dictionary<int, Employee>();

     

    这样我们就可以添加和删除员工信息了。

    Dictionary<K,T> 与 Hashtable 的不同之处还不止一处。除了支持强类型外,Dictionary<K,T> 还采用了不同的冲突解决策略(Collision Resolution Strategy),这种新的技术称为链技术(chaining)。

    前面使用的挖掘技术(probing),如果发生冲突,则将尝试列表中的下一个位置。如果使用二度哈希(rehashing),则将导致所有的哈希被重新计算。而新的链技术(chaining)将采用额外的数据结构来处理冲突。Dictionary<K,T> 中的每个位置(slot)都映射到了一个数组。当冲突发生时,冲突的元素将被添加到桶(bucket)列表中。

    下面的示意图中描述了 Dictionary<K,T> 中的每个桶(bucket)都包含了一个链表以存储相同哈希的元素。

    上图中,该 Dictionary 包含了 8 个桶,也就是自顶向下的黄色背景的位置。一定数量的 Employee 对象已经被添加至 Dictionary 中。如果一个新的 Employee 要被添加至 Dictionary 中,将会被添加至其 Key 的哈希所对应的桶中。如果在相同位置已经有一个 Employee 存在了,则将会将新元素添加到列表的前面。

    向 Dictionary 中添加元素的操作涉及到哈希计算和链表操作,但其仍为常量,复杂度为 O(1)。

    对 Dictionary 进行查询和删除操作时,其平均时间取决于 Dictionary 中元素的数量和桶(bucket)的数量。具体的说就是运行时间为 O(n/m),这里 n 为元素的总数量,m 是桶的数量。但 Dictionary 几乎总是被实现为 n = m,也就是说,元素的总数绝不会超过桶的总数。所以 O(n/m) 也变成了常量 O(1)。 

    参考:常用数据结构的时间复杂度

    参考:关于hash表的时间复杂度

    参考:面试中关于HashMap的时间复杂度O(1)的思考

    转载于:https://www.cnblogs.com/aspirant/p/8902285.html

    展开全文
  • List arrayList linkedlist ...add(index, E) 添加元素,在第几个元素后面插入,后面的元素需要向后移动,复杂度O(n) remove()删除元素,后面的元素需要逐个移动,复杂度O(n) 总结:查 0(1)

    List
    arrayList linkedlist
    arraylist 可增长的数组长度 查询快 get() set() 常数级
    插入和现有所有项的删除代价昂贵 除非在表的末端

    ArrayList 是线性表(数组)
    get() 直接读取第几个下标,复杂度 O(1)
    add(E) 添加元素,直接在后面添加,复杂度O(1)
    add(index, E) 添加元素,在第几个元素后面插入,后面的元素需要向后移动,复杂度O(n)
    remove()删除元素,后面的元素需要逐个移动,复杂度O(n)

    总结:查 0(1) 增 末尾0(1)中间0(n) 删0(n)
    移动是消耗时间复杂度的

    linkedlist 双链表 删快
    新项的插入和现有项的删除都是非常的快
    在表的前端添加和删除都是常数级
    addFristremoveFrist addLast removeLast getFirst getLast
    但是不容易做索引

    LinkedList 是链表的操作
    get() 获取第几个元素,依次遍历,复杂度O(n)
    add(E) 添加到末尾,复杂度O(1)
    add(index, E) 添加第几个元素后,需要先查找到第几个元素,直接指针指向操作,复杂度O(n)
    remove()删除元素,直接指针指向操作,复杂度O(1)

    总结:查 0(n) 增 末尾0(1)中间0(n) 删0(1)

    Set集合有三个常见的实现类:HashSet,TreeSet,LinkedHashSet。
    简单的说,如果你关注性能,应该使用HashSet;
    如果你需要一个有序的Set集合,应该使用TreeSet;
    如果你需要一个Set集合保存了原始的元素插入顺序,应该使用LinkedHashSet。

    HashSet是基于散列表实现的,元素没有顺序;add、remove、contains方法的时间复杂度为O(1)。(contains为false时,就直接往集合里存)
    总结:查 0(1) 增 0(1) 删0(1)

    TreeSet是基于树实现的(红黑树),元素是有序的;add、remove、contains方法的时间复杂度为O(log (n))(contains为false时,插入前需要重新排序)。

    总结:查 0(log n) 增 0(log n) 删0(log n)
    因为元素是有序的,它提供了若干个相关方法如first(), last(), headSet(), tailSet()等;
    LinkedHashSet介于HashSet和TreeSet之间,是基于哈希表和链表实现的,支持元素的插入顺序;基本方法的时间复杂度为O(1);

    待定
    总结:查 0(1) 增 0(1) 删0(1)

    map集合有三个常见的实现类:HashMap,TreeMap,LinkedHashMap。

    TreeMap基于红黑树(一种自平衡二叉查找树)实现的,时间复杂度平均能达到O(log n)。
    HashMap是基于散列表实现的,时间复杂度平均能达到O(1)。正常是0(1)到0(n) jdk1.8添加了 红黑树 是 0(log n)

    TreeMap的get操作的时间复杂度是O(log(n))的,相比于HashMap的O(1)还是差不少的。
    LinkedHashMap的出现就是为了平衡这些因素,能以O(1)时间复杂度查找元素,又能够保证key的有序性


    ————————————————
    版权声明:本文为CSDN博主「有趣的难受」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
    原文链接:https://blog.csdn.net/m0_37383866/article/details/87345539

    展开全文
  • 1. TreeMap 2. HashMap 3. ConcurrentSkipListMap 结果: 模拟150W以内海量数据的插入和查找,通过增加和查找两方面的性能测试,结果如下: Map类型 插入 查找(在100W数据量中)   10W ...

    比较Java原生的 3种Map的效率。
    1.  TreeMap
    2.  HashMap
    3.  ConcurrentSkipListMap

    结果:

    模拟150W以内海量数据的插入和查找,通过增加和查找两方面的性能测试,结果如下:

    Map类型插入查找(在100W数据量中)
     10W50W100W150W0-1W0-25W0-50W
    Concurrent
    SkipListMap
    62 ms227 ms433 ms689ms7 ms80 ms119 ms
    HashMap 18 ms93 ms217 ms303ms2 ms13 ms45 ms
    TreeMap 33 ms228 ms429 ms584 ms4ms34 ms61 ms


    分析说明
     

    图1- 1常数和logn函数效率对比示例图(横轴-n数据量,纵轴-f(n)时间)


    TreeMap基于红黑树(一种自平衡二叉查找树)实现的,时间复杂度平均能达到O(log n)。
    HashMap是基于散列表实现的,时间复杂度平均能达到O(1)。
    ConcurrentSkipListMap是基于跳表实现的,时间复杂度平均能达到O(log n)。

    如图所示:
    当数据量增加时,HashMap会引起散列冲突,解决冲突需要多花费一些时间代价,故在f(n)=1向上浮动。
    随着数据量的增加,HashMap的时间花费小且稳定,在单线程的环境下比TreeMap和ConcurrentSkipListMap在插入和查找上有很大的优势。

    (1) TreeMap与HashMap相比较

    Ø  HashMap里面存入的键值对在取出的时候是随机的,它根据键的HashCode值存储数据,根据键可以直接获取它的值,具有很快的访问速度。在Map 中插入、删除和定位元素,HashMap是最好的选择。

    Ø  TreeMap取出来的是排序后的键值对。插入、删除需要维护平衡会牺牲一些效率。但如果要按自然顺序或自定义顺序遍历键,那么TreeMap会更好。

    本测试增加和查找功能,HashMap比TreeMap的效率要高。

     


    (2) TreeMap与ConcurrentSkipListMap相比较

     

    Ø  Skip list(跳表)是一种可以代替平衡树的数据结构,默认是按照Key值升序的。Skip list让已排序的数据分布在多层链表中,以0-1随机数决定一个数据的向上攀升与否,通过“空间来换取时间”的一个算法,在每个节点中增加了向前的指针,在插入、删除、查找时可以忽略一些不可能涉及到的结点,从而提高了效率。
    从概率上保持数据结构的平衡比显示的保持数据结构平衡要简单的多。对于大多数应用,用Skip list要比用树算法相对简单。由于Skip list比较简单,实现起来会比较容易,虽然和平衡树有着相同的时间复杂度(O(logn)),但是skip list的常数项会相对小很多。Skip list在空间上也比较节省。一个节点平均只需要1.333个指针(甚至更少)。
                    
    图1-2 Skip list结构图(以7,14,21,32,37,71,85序列为例)

    Skip list的性质

    (1) 由很多层结构组成,level是通过一定的概率随机产生的。
    (2) 每一层都是一个有序的链表,默认是升序,也可以根据创建映射时所提供的Comparator进行排序,具体取决于使用的构造方法。
    (3) 最底层(Level 1)的链表包含所有元素。
    (4) 如果一个元素出现在Level i 的链表中,则它在Level i 之下的链表也都会出现。
    (5) 每个节点包含两个指针,一个指向同一链表中的下一个元素,一个指向下面一层的元素。

    Ø  ConcurrentSkipListMap具有Skip list的性质 ,并且适用于大规模数据的并发访问。多个线程可以安全地并发执行插入、移除、更新和访问操作。与其他有锁机制的数据结构在巨大的压力下相比有优势。

    查找功能在50W数据量以后,TreeMap更有效率,因为ConcurrentSkipListMap自带锁机制,会占用一些效率,但对于多线程并发的环境下,ConcurrentSkipListMap的效率会比Treep要好的。

    本测试查找方法使用Map的get方法,循环、离散获取。对于ConcurrentSkipListMap,获得顺序片段,可用subMap()方法,提取50w的子序列只需要1ms,具有巨大优势。 SkipListMap的范围查询效率比HashMap和TreeMap效率都要高。hashMap线程不安全,也实现Map接口的hashTable安全


    展开全文
  • 集合的时间复杂度

    千次阅读 2019-02-15 10:32:02
    List arrayList linkedlist arraylist 可增长的数组...get() 直接读取第几个下标,复杂度 O(1) add(E) 添加元素,直接在后面添加,复杂度O(1) add(index, E) 添加元素,在第几个元素后面插入,后面的元素需要向后...
  • 从1这点来看红黑树是牺牲了严格的高度平衡的优越条件为代价红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。 此外,由于它的设计,任何不平衡都会在三次旋转之内解决 。当然,还有一些更好的,但实现...
  • 且没有重复元素 O(1) O(1) O(1) Map HashMap 数组+(链表、红黑树) key不可重复 允许 键值存取,而且不要求顺序 时间复杂度平均能达到O(1)。正常是O(1)到O(n) jdk1.8添加了 红黑树 是 O(log n) O(log n) O...
  • Java集合时间复杂度

    2021-01-12 16:06:55
    TreeMap 基于红黑树(一种自平衡二叉查找树)实现的,时间复杂度平均能达到O(log n)。 HashMap是基于散列表实现的,时间复杂度平均能达到O(1)。正常是0(1)到0(n) jdk1.8添加了 红黑树 是 0(log n) TreeMap的get...
  • 其实这里的底数对于研究程序运行效率不重要,写代码时要考虑的是数据规模n对程序运行效率的影响,常数部分则忽略,同样的,如果不同时间复杂度的倍数关系为常数,那也可以近似认为两者为同一量级的时间复杂度。...
  • ArrayList常用方法时间复杂度 ArrayList底层数据结构是:数组 增加 add(E):尾部添加,时间复杂度O(1) add(index, E): 指定位置添加,时间复杂度O(N);指定位置添加后,需要将指定位置后面的全部元素向后移动一个...
  • JAVA各种集合操作的时间复杂度

    千次阅读 2019-04-15 19:47:00
    TreeMap基于红黑树(一种自平衡二叉查找树)实现的,时间复杂度平均能达到O(log n)。 HashMap是基于散列表实现的,时间复杂度平均能达到O(1)。正常是0(1)到0(n) jdk1.8添加了 红黑树 是 0(log n) TreeMap的get...
  • 每级遍历 3 个结点即可,而跳表的高度为 h ,所以每次查找一个结点时,需要遍历的结点数为3*跳表高度,所以忽略低阶项和系数后的时间复杂度就是 ○(㏒n),空间复杂度是O(n) 数据结构实现原理key查询方式查找效率...
  • HashMap和TreeMap对比

    千次阅读 2019-05-06 18:55:52
    jdk1.8在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为8)时,将链表转化为红黑树,以减少搜索时间。 HashMap JDK1.8 之前 HashMap 由 数组+链表 组成的,数组是 HashMap 的主体,链表则是主要为了...
  • 但是HashMap还是有自己的局限性----它不具备统计性能,或者说它的统计性能时间复杂度并不是很好才更准确,所有的统计必须遍历所有Entry,因此时间复杂度为O(N)。 比如Map的Key有1、2、3、4、5、6、7,我现在要统计:...
  • Java 中的 Map 是一种键值对映射,又被称为符号表或字典的数据结构,通常使用哈希表来实现,但也可使用二叉查找树、红黑树实现。 HashMap 基于哈希表,但迭代时不是插入顺序 LinkedHashMap 扩展了 HashMap,维护了...
  • LinkedHashMap,TreeMap

    2019-11-25 22:54:57
      继承 HashMap,因此具有和 HashMap 一样的快速查找特性。内部维护了一个双向链表,可以实现散列数据结构的有序遍历。LinkedHashMap可以用于实现 LRU 缓存。LRU手撕   HashMap 底层基于拉链式的散列结构,并在...
  • Java面试题大全(2020版)

    万次阅读 多人点赞 2019-11-26 11:59:06
    发现网上很多Java面试题都没有答案,所以花了很长时间搜集整理出来了这套Java面试题大全,希望对大家有帮助哈~ 本套Java面试题大全,全的不能再全,哈哈~ 一、Java 基础 1. JDK 和 JRE 有什么区别? JDK:Java ...
  • Java 集合时间复杂度

    2021-06-04 20:51:40
    get() 直接读取下标,复杂度 O(1) add(E) 直接在队尾添加,复杂度 O(1) add(index, E) 在第n个元素后插入,n后面的元素需要向后移动,复杂度 O(n) remove() 删除元素后面的元素需要逐个前移,复杂度 O(n) ...
  • HashMap和TreeMap区别详解以及底层实现

    万次阅读 多人点赞 2015-08-23 18:23:12
    前言首先介绍一下什么是Map....HashMap通过hashcode对其内容进行快速查找,而 TreeMap中所有的元素都保持着某种固定的顺序,如果你需要得到一个有序的结果你就应该使用TreeMap(HashMap中元素的排列顺序是不固定的
  • 本资源提供了List对对象中的属性和TreeMap, String>对键值排序,并针对100w条数据排序,对比List和TreeMap, String>排序的效率。个人认为排序效率对比可以相信,但也可能存在不科学之处,还请高手给与指点,多多包涵...
  • 如果在开发中需要对元素进行排序,那么使用 HashMap 便无法实现这种功能,使用 TreeMap 的迭代输出将会以元素顺序进行。LinkedHashMap 是基于元素进入集合的顺序或者被访问的先后顺序排序,TreeMap 则是基于元素的...
  • HashMap的插入查询删除的复杂度

    千次阅读 2020-06-19 10:55:47
    1.各种java常见的数据结构的时间复杂度? | 数据结构 | 查找 | 插入 | 删除 | | :------------------------------------- | :----- | :----- | :----- | | 数组ArrayList | o(n) | o(1) | o(n) | | 有序数组
  • 给定一个数组,将数组里的偶数要在奇数前面,要求时间复杂度位O(n) 例如: 输入 data = { 1 ,2 ,3 ,4,5,6,7,8,9,0,13} 输出 data={0,2,8,4,6,5,7,3,9,1,13} 备注:仔细观察输入和输出,仅仅是将前面的奇数和后面的...
  • 基本操作 containsKey、get、put 和 remove 的时间复杂度是 log(n) 。 另外,TreeMap是非同步的。 它的iterator 方法返回的迭代器是fail-fastl的。 1、属性 2、构造方法 记得继承SortedMap建议实现的四个...
  • Java集合面试题

    万次阅读 多人点赞 2019-06-25 14:46:19
    JDK8 以后,在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为 8 )时,将链表转化为红黑树,以减少搜索时间。 LinkedHashMap :LinkedHashMap 继承自 HashMap,所以它的底层仍然是基于拉链式散列...
  • 和普通的HashMap不一样,普通的HashMap元素存取的时间复杂度一般是O(1)的范围。而TreeMap内部对元素的操作复杂度为O(logn)。虽然在元素的存取方面TreeMap并不占优,但是它内部的元素都是排序的,当需要查找某些元素...
  • 集合、数据结构、时间复杂度 1、集合 1.1 概述 java集合分为三种类型,List、set和Map。List有序,可以重复。Set无序不重复。Map是Key-value对类型,其中Key具有set的特点。 1.2 List List java中有ArrayList和...
  • 测试开发面试题汇总

    千次阅读 2019-07-30 18:01:07
    10.排序和算法的时间复杂度&空间复杂度 冒泡排序:O(n2) O(1) 插入排序:O(n2) O(1) 选择排序:O(n2) O(1) 二叉树排序:O(n2) O(n) 快速排序: O(n2) O(log2n)~O(n) 堆排序: O(n*log2n) O(1) 希尔排序:O O...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,693
精华内容 4,277
关键字:

treemap查找时间复杂度