What a fricking meme of a data structure.
>if it's small items it's pointless.
>if it's large it takes up an insane amount of memory
>collisions make it O(n)...like fricking iterating through an array
>converts strings to number...bytes are number why bot just use them directly?
>a lot of work to achieve minimal results
>collisions make it O(n)...like fricking iterating through an array
Use a self balancing tree moron
>Use a self balancing tree moron
This implies the fricking moronic OP can implement one.
>a tree is a hash table!!!
the point ---------->
(You)
Go back to class you dumb frick.
Okay moron. Lets say I allocate enough space to hold 1 million elements...tell me what happens when you run clean up code before you kill your program?
You're gonna iterate through it and free any used memory. 0(n).
If you allocate space 256 elements any modern day computer from 2000+ can iterate through 256 elements fast enough to not make a difference between O(n) and O(1). You're just wasting your time.
>Okay moron. Lets say I allocate enough space to hold 1 million elements...tell me what happens when you run clean up code before you kill your program?
>You're gonna iterate through it and free any used memory. 0(n).
This applies to literally every data structure dumbass, iteration over the elements is O(n) by definition, what's your point?
Hash tables also often overprovision memory and reallocate before the entire table is full so as to avoid collisions, at the cost of extra memory
If that risk really is somehow a problem to you, just switch to a btree with consistent O(log n) performance on most operations
First of all, I know about btrees moron. We are talking about hashtables.
The point is that modern day processors are fast enough to barely make a noticeable difference. Hash tables are purely for searching. Linked Lists and Arrays can search at O(n). Linked Lists can do it while saving memory and they're indexed too.
In hash tables you may not know what's were and , what's what. If you use RAII, you're ultra fricked if you use a large hash table in a function.
>If you use RAII, you're ultra fricked if you use a large hash table in a function.
You only use a large hash table if you need a large mapping, and if you need a large mapping then it's one of the better options. You don't generally put a big hash table into every function just in case you need one.
You're coming across as a complete midwit, able to understand what things do, but not able to understand the costs of the alternatives and why some things shouldn't be worried about.
All competent non toy hash table implementations use linear probing because of cache locality you absolute frickwit.
This, there's been a noticeable uptick of DK morons like op on IQfy in the last couple of years
>linear probing
That's O(n) no? So the hashmap at its worse case is O(n) no?
Hash maps are a tradeoff between space and performance. Thus, if linear probing gives you a 50x speedup compared to eg. cuckoo hashing (true O(1)) or quadratic probing, you use that instead of everything else. There's also certain other schemes that augment linear probing like robin hood hashing (essentially LRU for probing) but statistically linear probing works out given reasonable table size and performance expectations.
>Hash tables also often overprovision memory and reallocate before the entire table is full so as to avoid collisions
Litterally what I was going to say.
This is a long process that takes O(n) to do. Your gonna O(n) forever, if you want to avoid collisions in this manner.
>Your gonna O(n) forever, if you want to avoid collisions in this manner.
Seriously, look stuff up in an algorithms text book. That *WILL* have a chapter on hash tables, they are that important, and why they normally work well is a subtle point.
>If that risk really is somehow a problem to you, just switch to a btree with consistent O(log n) performance on most operations
Unless you take a great deal of care, the btree may end up using more space than the hash table. Memory allocations are very much not free (Oh, and many of those mitigations are also applicable to hash table implementations, except people don't normally bother; keeping the code size small is its own benefit.)
>You're gonna iterate through it and free any used memory. 0(n).
Pull the power cord out - memory cleared at O(1).
>You're gonna iterate through it and free any used memory. 0(n).
You tell the OS that your program is ending and it marks all the addresses assigned to the program as now free.
In a perfect world it works like that. Unfortunately you can't work like that with instruments. Your instrument will remember it's last state. Also sometimes you want to grab the data and before you shutdown for analysis.
>You're gonna iterate through it and free any used memory. 0(n).
Ever wondered how those tools to recover deleted data / dead drives work?
Most of the times the OS doesnt iterate, its left as is and mark that a given range of memory is empty. It doesnt go through it byte by byte and write zeroes on all of it.*
*usually, some autistic linuxers and corpos prefer to waste their writes on zeroing but its not worth it my man
it's useful if you're selling a used HDD/computer
Ok point taken. Thats an exception.
In cases where you absolutely need something that is slow to do done, you do it, yes.
>when you run clean up code before you kill your program
based moron
freeing memory before killing your program is pointless because all memory used by the process gets freed by the OS when you kill it lol, lmao
Not if you're interfacing with hardware. Your program shuts down but the hardware doesn't. E.g. I have 2 processes running and I used P1 to ask P2 to dynamically allocate memory for some data. When P1 is about to shutdown, it asks P2 to clean up. P1 is not allowed to shutdown until P2 acknowledges that P1's data has been removed.
P2 would still just clear the pagetable for P1.
P1 and P2 are 2 completely separate process. P2 could have out sourced my data to a number of processes and could crash while awaiting their response.
If that happens P1 will abort shutdown then attempt to revive P2 and ask him to try again or confirm if the data is definitely gone. It is imperative that P1 knows the data is gone. No guess work. No ifs no maybes.
That's what self healing actors are. It's a super robust system .
Read up on Actors.
Still can't see why it would need to iterate through the hashtable.
Again, you don't have to zero out memory, you don't have check each value for anything.
You're just defining a program that has to iterate through the hashtable, and then saying that hashtables are bad because a program that has to iterate through the hashtable, has to iterate through the hashtable.
>Still can't see why it would need to iterate through the hashtable.
Because you allocate memory for the hash table the allocated memory for the values in tbe hashtable. Deleting the hash table will only delete the memory allocated for the hash table but not the memory for the values.
You allocate memory for the values because you want to copy data aka pass by value. If you don't you're just passing by reference. Also you only know the size of the data when it needs to be allocated.
TLDR: It's a hash table that holds pointers to malloced values. On exit of P1, P2 needs to delete the Hash table mallocs as well as the pointers contained in it, then inform P1 that it has done it.
P2 cannot shutdown because other processes also want to use P2.
>A hash table occupies a contiguous chunk of memory
No. Not if your hashtable contains pointers. You freed the hash table but not the items the pointers point to.
You want to delete both the table and it's items. You have it iterate through the table. The hashtable is like a python list. It can hold multiple types.
Actors require messages. Messages hold information. That information can be anything and any type. All I know is that I have an envelope with an address. I store all envelopes for that address in a bucket and that actors will retrieve it from the bucket when it's ready.
Actors are not about memory management. They're about rubust, secure, self healing and asynchronous processes working together to form a system.
>he doesn't know about open addressing
anyway, the problem you're having is due to your distributed memory management system, not due to using a hashtable. in your silly system, even a contiguous array could be split across multiple processes, so the point is moot.
any and all data structures will suffer at the hands of your system
>contiguous array could be split across multiple processes
Process dont share memory homosexual. Does Chrome share memory with Microsoft word?
You can't be this moronic. This isn't multithreading. It's multiprocessing.
read the thread moron. the homosexual OP is talking about some bullshit self healing actor system, not a normal OS.
That "gay" is me. Actors are processes not threads. moron. If they were threads then they can't self heal. A segmentation fault will kill the program/system.
>P1 and P2 are 2 completely separate process. P2 could have out sourced my data to a number of processes and could crash while awaiting their response.
moron
Yes. Actors communicate through messages. If they can't communicate then how the frick does any work get done? moron.
what if instead of communicating via messages you used a pattern that actually vibes with the hardware you are using? unless that is, you have a hardware implementation of the erlang vm that provides better perf than our ludicrously optimized von noimann machines.
>what if instead of communicating via messages you used a pattern that actually vibes with the hardware you are using?
"Use messages" doesn't say the exact method by which messages are sent, moron. There's lots of possibilities, but high level code doesn't usually need to care about the details as long as the low level gets it right.
>Actors are processes not threads. moron. If they were threads then they can't self heal. A segmentation fault will kill the program/system.
You are Ctarded. Message passing only needs you to link a few pointers.
Can't link pointers. It's a process. How does Microsoft Word link a pointer to Firefox? They are 2 separate processes. They don't share a memory space. It's not multithreading you dumb frick.
Read up on IPC. Yes I could use Pipes, but have you tried to work with pipes?
>Because you allocate memory for the hash table the allocated memory for the values in tbe hashtable.
It sounds like you're positing a system with no memory management, so every process has to manage its own memory, and P1 is running the memory management.
But you're structured it in such a convoluted manner that it will be slow by design, then blaming hash tables for it being slow.
>so every process has to manage its own memory
Yes, congratulations. You get it. Every program in you computer manages it's memory. They are processes that work together to form a system.
P3 for example could handle all the work required for the UI. P2 simply exists to log data and return the results. P1 exist to process sensitive data once in a while, it shutsdown when done and is revived when needed.
>slow
It's not slow. Processes exist when they need to. Processes asynchronous. You run what you need when you need it. The UI will never lag.
The system is robust and hard to kill. Only when to kill it is to do it intensionally. e.g. the user presses the close button on P3 and P3 sends a message to Every process to run its clean up code before shutting down.
>Every program in you computer manages it's memory.
Superficially. Most of the actual management is done in the OS and hardware, but you're describing a system where the program takes on those roles as well and then saying that a hash table isn't O(1) because when you iterate through it it's O(n).
Which is moronic.
I'm saying P2 is a logger. P1 wants to shutdown and wants P2 to delete all data associated with it. Data in P2 can be of any type. Lets assume P2 uses a hashtable to log P1's data as requested by P1. P1 wants a specific subset of the data to logged by P2. When P1 obtains the results it needs. It asks P2 to delete all data associated with it. When that is done P1 shutsdown. P2 doesn't because another process wants to use it or is using it.
Now let's step back. P2 is a logger. It can log data of any size and any type. It stores this data in a hashmap so it's easy to search through it. To do this I chose to store pointers in a hashmap. Those pointers point to data that has been dynamically allocated. I have a billion items in that hash table. That's a billion memory allocations. Deleting the Hashtable only deletes the hashtable but not the billion mallocs. Those are now orphaned. To avoid that scenario you have to iterate through the hashtable and free each element before you delete the hashtable. That operation will take O(n) time if there are no collisions. If there are collisions were talking O(n^2). I could save myself the headache and just use a skip list. Sure searching will be slower (if there are no collisions) by but cleaning up will be faster and more reliable.
>and wants P2 to delete all data associated with it.
So slow by design.
>To do this I chose to store pointers in a hashmap. Those pointers point to data that has been dynamically allocated. I have a billion items in that hash table. That's a billion memory allocations. Deleting the Hashtable only deletes the hashtable but not the billion mallocs. Those are now orphaned. To avoid that scenario you have to iterate through the hashtable and free each element before you delete the hashtable.
So bloated and slow by design.
>So slow by design.
Memory needs to be freed anon.
>So bloated and slow by design.
This is how every programming language that isn't C works. Your garbage collected shit works this way.
dying laughing
The moment he mentioned being inspired by python for his performance sensitive framework it was over. Then he had to steal python's dumbest idea of storing everything in heap objects lmfao
Python is slow because it's interpretating. It has to read a script for disk and compile shit JIT. There is no JIT here. SQL databases also work like this. How would you create a hashmap that would hold a generic type in C without using pointers?
*There is no JIT compilation here.
If all the types held in the hash table are the same then you allocate once for the entire underlying array of the hash table.
Types in the hash table are not the same. One key's value can be an array of floats the other can be a linke list of string. You will never know.
>Python is slow because it's interpretating
Python is slow even by the standards of interpreters, and that's despite being bytecode compiled.
You're artificially imposing additional complexity with your garbage distributed system that apparently has an utterly moronic clusterfrick of a memory management system.
A hash table occupies a contiguous chunk of memory, which is trivial to deallocate. If your shitty system is strewing chunks of memory all over the place, that's on you, not the hash table, which is basically just an array.
In a normal OS, when P1 is killed it's basically free to deallocate its memory, you wouldn't iterate over its data structures freeing them manually because that's fricking moronic.
This sounds extremely fishy.
Why would you iterate through the hashset to free up the memory? You don't have to zero out memory to "free" it, all you have to do is tell wherever you requested memory from that the addresses you were allocated are now free.
>I must write 0s over every bit of memory I have touched in the computer before I close my program
I think you just invented a program more diabolical than C, BUT, you will never, EVER encounter a seg fault. You need to start writing your TED talk now, and order a new pair of pants for all of computer science.
see
>if it's small items it's pointless.
Not necessarily. It's the typical choice for when you want to use strings as keys, since how the frick else are you going to turn a string into an array index? And do you really want to do string comparisons on every key every time you search? Gross!
>if it's large it takes up an insane amount of memory
Large data structures by necessity take up a large amount of memory. That said, a hash table is not necessarily wasting memory.
>collisions make it O(n)...like fricking iterating through an array
O(n) worst case, O(1) average case. Learn what amortization means when evaluating time and space complexity. Vectors are another data structure that has an amortized O(1) operation. Pushing an element at the end of a vector can take up to O(n) time if it has to reallocate, or it can take O(1) if you have memory to spare. By doubling your allocation size every time you need to reallocate, the amount of time spent copying over data is reduced significantly.
>converts strings to number...bytes are number why bot just use them directly?
Computing an array offset expects a number that is fixed in size. Preferably between 0 and however many bytes you have in your buffer. Strings have an arbitrary size. To make them useful as an array offset... you need to compute a hash over them.
>a lot of work to achieve minimal results
You have never worked on any project where performance matters, so you might as well stop talking out your ass.
You have a data structure containing millions of (key, value) pairs. This data structure is going to persist in memory for a period of time that can be measured in days, not seconds. During this time, there are going to be millions of accesses on arbitrary keys. If each of those million accesses has to involve iterating through a million keys, performing a string comparison every time, then you're doing trillions of string comparisons. That's gonna hurt.
>It's the typical choice for when you want to use strings as keys, since how the frick else are you going to turn a string into an array index?
How about you don't? Strings only exist for UI/logging purposes. They're for humans to read not machines.
Using string in a hash table for small tables wastes more performance as you have to loop through each character to generate a hashcode. No need to loop with numbers. Array love you long time.
All data that is input from a file or network socket or any other form of program input... is going to be a string. Turns out in a significant number of cases, using strings as keys is mandatory.
>All data that is input from a file or network socket or any other form of program input... is going to be a string
No. It's all binary. Ever heard of serialisation and deserialisation? Over opened a .db file created using SQL? What a .exe file? You can't read shit.
You shouldn't be using strings as a key unless it's for UIs or writing human readable shit in a file.
>writing human readable shit in a file
You mean like code in large pieces of software that other developers will have to be able to understand in 2 years? Dumbass.
>You shouldn't be using strings as a key
How to show you're still a junior programmer: the post.
i am stupid and even I know you don't have to bother to zero the memory in the first place
You definitely are stupid if you think free()
is for zeroing shit. free() releases memory back to the process's heap manager. It's basically saying hey! this space is free for you to use now.
>hey! this space is free for you to use now.
>free(OP.bussy);
>thinking computers free memory one byte at a time
Based moron
homie I think you may be moronic
You really do need to study more. In particular, you need to study the expected length of the lists that hang off the back of the hash table. Theoretically you don't need them if you can do perfect hashing, but nobody sane does that. (There's also open addressing, but that's worse when the table starts to get full. I can't remember the load threshold where that becomes a problem.)
But don't take my word for it. Find some good implementations and measure the cost of putting elements in, looking them up a bunch of times in various patterns, and then deleting the lot.
Also you can use a string as a number directly. But you don't normally as a string of 80 bytes long isn't a very long string, but a number of 80 bytes (640 bits) is a pretty big number; ain't nobody need numbers that big for hashing!
>you can use a string as a number directly.
The problem with strings is that you have to loop through the bytes O(n) then apply your hash function then hope the user doesn't use a certain order of strings that will cause collisions essential turning your table O(n).
>The problem with strings is that you have to loop through the bytes O(n) then apply your hash function then hope the user doesn't use a certain order of strings that will cause collisions essential turning your table O(n).
The number of strings you have is not normally proportional to the length of those strings. In theory, it's possibly related to the log of the number of strings, but in practice it never is. That's why you use a different variable, say M, for the average string length. At that point, you can say that computing the hash code of a string is usually O(M), with the cost of that calculation not ever depending on the number of different strings you've got. There are hash functions that are constant cost, but they tend to be shit. (A simple example is "only use the first four bytes of the string, and interpret those directly as a 32-bit number". It's an O(1) algorithm, and it's a pile of shit in practice; only PHP has ever used hash functions that bad, and that was because its developers were moronic frickwads.)
Perfect hashing is no problem to use for constant lookup tables. gperf can genarate these automatically
it's the same pajeet moron from previous thread who didn't even know what hash is 2 hours ago
this moron is probably trying to self teach but he's too stupid to understand the material
go to college dumbfrick
nah its just your average corpo codeslave that managed to charisma his way into a job he can't handle aka 90% of 'professionals'
>so mad he made a new thread about it
>still doesn't understand it
Wow, I spwanned a thread lol
Alright, with what should we replace hash table, in the general case ? Some tree or something ?
>in the general case
when you only have a hammer, everything looks like a nail.
When all you have is a hammer, everything looks like a finger.
i never understood this banner. for some reason it reminds me of the hawaiian punch one, which i don't get either
Ok so what are examples of partial replacements ?
the point is a good software engineer chooses the appropriate data structure for the task at hand. there is no silver bullet data structure that solves all your needs, and if you program like there is one, you are likely a shitty programmer.
Yes, well, being educated in any scripting language where you can technically encode any data structure but you are forced to used hashes everywhere because there are no structs forces you to think that way
it would be great to have a scripting language that also lets you manage memory if you want to, but if I understand correctly, it would conflict with the garbage collector
If you're not using strings as keys just use an normal array.Strings are pointless as keys because you're gonna loop through them and there is nearly an endless combination of them making collisions 300,000% likely. Heck they will happen so frequently it it's insane.
binary trees, skip lists, regular old arrays are always good. No bullshit, it just works and they take advantage of the bare metal
>skip lists
I didn't know this one thanks
Do you know if the other kind of trees are good or are they only wanking ? Like red-black trees, AVL trees, Hash array mapped tries, etcc
I'm just getting to know C at an intermediate level, I have to adapt to not using hashes everywhere lol
It's true that a lot of the time, we're just using strings as a kind of symbol
Why do cstards think data structers are pokemon where you send out the 'right' one? use the standard library version of the one that fits and if they're all a bad fit then make one that fits the problem with a class.
Btree is the logical replacement. Sorted lists are just fine if it's mostly lookup and not insert.
your replacement to do your job more effectively/
here is ur pink slip
Idiot
is this the new way to ask for help with your homework?
no. However I am working on an Actor Framework that is self healing. It's a personal project.
https://www.cs.wcupa.edu/rkline/ds/hash-sets.html
Full rundown from an academic source in case one of the crypto nazis here puts in some right wing prop. into their answer
Because Black person cattle academics funded by ~~*Soros*~~ push globohomosexual computing and zoomers eat it all up like the bugs they are commanded to eat and ~~*(vaxx*~~)
White Men never needed hash tables. White Men built UNIX and OPEN SOURCE and ARPANET all without hash tables.
strings to number...bytes are number why bot just use them directly?
based moron
>hashsets are better than sets because... because it's O(1) for lookup/insertion and for sets its O(log(n))
log(n) is basically O(1)
if you have 10^100 items in your set log(10^100) = 100 * log(10), so you expect lookup from a set with one googol elements to only be 100 times slower than a set with 10 elements. in reality your sets are never so big for it to actually make a significant difference.
>log(n) is basically O(1)
based. I think I'll stick to skip lists then.
This. 30 steps can binary search a billion elements. Good luck hashing and handling collisions in 30 steps.
this thread is why i just implement both solutions and benchmark them
Not sure if it was OP’s intention, but this thread is a good example of how if you want IQfy to spoonfeed you knowledge, all you have to do is pretend to be stupid and make bold claims that people will climb over each other to correct.
based
>implement both solutions and benchmark them
Sensible, as long as your benchmark is realistic with respect to what you're doing at the end. (For example, if you're going to be storing many short words then use the contents of /usr/share/dict/words as your benchmark dataset).
>O(n) for collisions
if you implement it like a brain dead moron yea. use a b-tree per bucket instead you god damned simpleton.
Totally agree. Hashing is gay. Sorting is Chad.
didn't we just have this thread?
>literally every thread on IQfy in a nutshell
what if we made it again in like 6 hours!? doooooooooooood wow that will be so much fun omggggg
All data structures have pluses and minuses, though some are really better than others. Like the various linked lists, which are basically replaced by Vectors in C++, or I guess you could also do Dictionaries in Python, which assigns a keyword to each entry. Maybe there's something similar in C/C++, probably.
Here's the thing anon, computers have resources, and you have to decide how to use those resources for your purpose. Would you rather use more RAM, or more CPU power? Depends on your application and what you're trying to *achieve* overall.
Assuming that your hash function is "perfect" and "never collides", then having O(1) is great. Saves CPU time but uses more ram. If you need a list to iterate through, then use an array, LL/Vector, or similar in your programming langue of choice. It will use more CPU time for O(n), but may or may not be more efficient on memory.
In the real world, on real, decent hardware, does O(1) matter over O(n)? Probably not. You can even cache frequently used values with pointers/reference variables in case you want to access something over and over again after you search for your entry.
But yeah, the biggest downside to a hash table is you can't iterate through it. But it's not made for that purpose.
Like people have said, go take CS in college and learn data structures. They will tell you all the same shit about benefits and weaknesses of things.
The equivalent in C++ (no standard implementation in C afaik) is unordered_map, but there are a few more steps like having to specify the equality/hash functions for all but the most trivial keys. It's also dogshit slow compared to other more optimized hashtables.
>if it's small items it's pointless.
It's still useful if you have a large number of items and need to find specific ones. Or if most of the items are things you don't care about like the locations of 0s in a sparse matrix.
>if it's large it takes up an insane amount of memory
It's more overhead than an array, but not as much as you think.
>collisions make it O(n)...like fricking iterating through an array
That depends on how you implement the hashtable. And you only need to worry about O(n) if you or the user somehow deliberately create items so that they all map into the same bin.
>converts strings to number...bytes are number why bot just use them directly?
You could just work off of the byte representation of the string if you really wanted to. But hash functions can have some useful properties like avoiding collisions between similar items, or behaving as an abstraction so that you can put all sorts of other complicated objects into a hash table as long as you have a matching hash function for them.
>a lot of work to achieve minimal results
Depends on the language. In C/C++, sure, it's more work than just using an array. But in other languages it's not that much more complicated.
>if it's large it takes up an insane amount of memory
Yes. That's the point. To take something cheap and horizontally-scalable to offset computational costs.
Memory topology and cache lines and latency tho
>O(1)
My ass. Best you can hope for is a DeBruyne graph kind of structure and even that takes a big chunk of time and memory to set up an index and is only useful if you're indexing once and mapping many times.
A lot of "seniors" in my company literally just uses Black personlicious linked lists everywhere, trees and hashmaps are nowhere to be seen, they keep doing dynamic memory allocations during runtime unnecessarily, and everybody wonders why everything is so slow.
This is a gayMAN company.
no bro, its nlogn(O) bro
we got too wienery bro
The big advantage to hash tables is O(1) lookup time in the best case, when is most of the time if the hash table is properly sized
most of the time, lookups are O(1) and with some variation on linear probing, you are very likely to have your item in cache even in case of collision
if you have data that results in lots of collisions and you can't improve your hash function, use a tree you fricktard
Wow! So O(1) relies on hopes and dreams? kek. Shut is O(n) in the worst case no matter how you look at it unless you use a Binary search tree or a skip list as a bucket.
The O(1) shit is a meme. Hopes and fricking dreams.
No, it's amortized O(1), which is not the same as worst case O(1). See
See
>There better alternatives if it's large, there are better alternatives if it's slow.
>Using strings as key is pointless unless you guessed every single string combination and aren't gonna loop through characters before insertion
>If you're not gonna use strings, bing ints instead why not just use an array?
>only useful keys which are floats.
>Takes a long time to implement only to achieve O(n) at the end of the day
Congratulations. Looks you agree with OP. Mordern computers are fast enough to handle O(n) operations at unnoticeable speeds. Why even bother unless you're working with 90s hardware?
better alternatives if it's large, there are better alternatives if it's small*
If the collision count reaches eg. 50, you do a rehash, potentially also a resize. The value 50 does not scale with the size of the hash table itself, and so O(50) for worst case search and delete.
Given a good enough resize strategy, you'd be able to insert n elements before having to increase the array size by 1.3n where 1.3 is an example average load factor, thus O(n)/O(n) or O(1) amortized.
Sorry to break it to you, but it's not O(n). You can argue that insert is akchually not O(n) but that's pretty much never ever the case. Everything else you mentioned is just moronic and not worth refuting.
not O(1)*
>See [my own moronic post, that was already mocked by dozens of anons]
Why do you schizos keep acting like this?
Take your meds and choke on them, homosexual, you won't be missed.
You sound mad. Why? Did I say something uncomfortable?
>relies on hopes and dreams
No, it relies on averages over sequences.
>in the worst case
Yes, how often does your input hit that case? My bet is that it's a set with measure 0, hence Θ(1).
>No, it relies on averages over sequences.
you mean hopes and dreams?
>Yes, how often does your input hit that case?
If it can happen it will happen. No amount of hoping and dreaming will prevent such a scenario from occurring.
No, i mean averages and sequences.
>If it can happen it will happen
Of course it will, but the incidence tends to 0% as you increase N.
If you take the easiest 2^k resizing strategy which isn't even optimal, it happens n + sum(n/2k) and additional n for the first lookup, 3n ~ O(n).
>So O(1) relies on hopes and dreams?
Try measuring it with real data, moron.
It's never O(n), even if you have collisions occasionally