რამდენი დრო სჭირდება ახალი ელემენტის დამატებას ლექსიკონში?

ნუის ელემენტის დამატების დროითი სირთულე ლექსიკონში (მაგალითად, Swift-ის Dictionary ან Objective-C-ის NSMutableDictionary) ჩვეულებრივია O(1) საშუალოდ. ეს განპირობებულია იმით, რომ ლექსიკონი რეალიზებულია ჰეშ-ცხრილის საფუძველზე, სადაც ჰეშის გამოთვლა და ჩაწერა ხდება კონსტანტული დროით.

თუმცა, ყველაზე უარესი შემთხვევებში, კოლიზიების ან შიდა მასივის გაფართოების საჭიროების შემთხვევაში, სირთულე დროებით შეიძლება გაიზარდოს ორჯერ O(n)-მდე, სადაც n ელემენტების რაოდენობაა.

Swift-ის მაგალითი:

var dict = [String: Int]()
dict["key"] = 42 // საშუალოდ დამატება O(1)