# Is lookup and insert really constant time in Erlang ETS set? **URL:** \ **Category:** Questions / Help\ **Tags:** erlang, ets\ **Created:** [February 27, 2024, 12:56pm UTC](https://erlangforums.com/t/is-lookup-and-insert-really-constant-time-in-erlang-ets-set/3335 "2024-02-27T12:56:24Z")\ **Posts on this page:** 10\ **Page:** 1
**Author:** ![Inforista](https://erlangforums.com/user_avatar/erlangforums.com/inforista/32/2279_2.png) [@Inforista](https://erlangforums.com/u/Inforista)\ **Post date:** [February 27, 2024, 12:56pm UTC](https://erlangforums.com/t/is-lookup-and-insert-really-constant-time-in-erlang-ets-set/3335/1 "2024-02-27T12:56:24Z")
The erlang doc states that: > Insert and lookup times in tables of type `set` are constant, regardless of the > table size. How is erlang ets set key/value tables implemented internally? If it is by a hash table - will it not be nessasary to recalculate the hash adress space once in a while and thus it is not β€œpure” constant lookup time? ---
**Author:** ![sverker](https://erlangforums.com/user_avatar/erlangforums.com/sverker/32/841_2.png) [@sverker](https://erlangforums.com/u/sverker)\ **Post date:** [February 27, 2024, 1:10pm UTC](https://erlangforums.com/t/is-lookup-and-insert-really-constant-time-in-erlang-ets-set/3335/2 "2024-02-27T13:10:45Z")
Ets `set`, `bag` and `duplicate_bag` are hash tables that grow and shrink dynamically one bucket at a time using [linear hashing](https://en.wikipedia.org/wiki/Linear_hashing). ---
**Author:** ![Inforista](https://erlangforums.com/user_avatar/erlangforums.com/inforista/32/2279_2.png) [@Inforista](https://erlangforums.com/u/Inforista)\ **Post date:** [February 27, 2024, 1:14pm UTC](https://erlangforums.com/t/is-lookup-and-insert-really-constant-time-in-erlang-ets-set/3335/3 "2024-02-27T13:14:13Z")
Thank you @sverker πŸ™‚ Will read up on linear hashing right away 😊 ---
**Author:** ![sverker](https://erlangforums.com/user_avatar/erlangforums.com/sverker/32/841_2.png) [@sverker](https://erlangforums.com/u/sverker)\ **Post date:** [February 27, 2024, 1:31pm UTC](https://erlangforums.com/t/is-lookup-and-insert-really-constant-time-in-erlang-ets-set/3335/4 "2024-02-27T13:31:54Z")
The ETS hash implementation is a segmented array of buckets, where each segment contains 256 buckets. When the first initial segment, with buckets 0-255, is β€œfull” we allocate a new segment, with buckets 256-511, and start splitting bucket #0 into bucket #0 and bucket #256 by using one more bit of the hash value. Then we split bucket #1 into #1 and #257 and so on. When we have all 512 buckets used and the table is considered β€œfull” again we allocate yet another segment and start over by splitting bucket #0 into #0 and #512 by using yet another bit of the hash value, and then bucket #1 into #1 and #513… ---
**Author:** ![Inforista](https://erlangforums.com/user_avatar/erlangforums.com/inforista/32/2279_2.png) [@Inforista](https://erlangforums.com/u/Inforista)\ **Post date:** [February 27, 2024, 1:56pm UTC](https://erlangforums.com/t/is-lookup-and-insert-really-constant-time-in-erlang-ets-set/3335/5 "2024-02-27T13:56:15Z")
Thank you @sverker for this detailed explanation πŸ‘Œ ---
**Author:** ![Inforista](https://erlangforums.com/user_avatar/erlangforums.com/inforista/32/2279_2.png) [@Inforista](https://erlangforums.com/u/Inforista)\ **Post date:** [February 27, 2024, 2:04pm UTC](https://erlangforums.com/t/is-lookup-and-insert-really-constant-time-in-erlang-ets-set/3335/6 "2024-02-27T14:04:19Z")
Actually, with this ETS hash implementation - are there β€œedge” cases there can break the ETS table? For ETS set tables … in principal can you have an unlimited size table, where only limit is the RAM size of the system? Like TB of RAM … will the ETS set table still work in this extreme case? Or are there physicial limitations I need to concider for really extreme use of ETS set tables? ---
**Author:** ![sverker](https://erlangforums.com/user_avatar/erlangforums.com/sverker/32/841_2.png) [@sverker](https://erlangforums.com/u/sverker)\ **Post date:** [February 27, 2024, 3:21pm UTC](https://erlangforums.com/t/is-lookup-and-insert-really-constant-time-in-erlang-ets-set/3335/7 "2024-02-27T15:21:44Z")
Well, as you ask, I checked, and it seems we keep the total number of buckets in a 32-bit signed integer. So, if you can fill a table with more than 2 billion keys you might hit that limit. If I calculate correctly that would demand an absolute minimum of 128 Gb of memory. That is easy to fix, and we should probably do it. ---
**Author:** ![Inforista](https://erlangforums.com/user_avatar/erlangforums.com/inforista/32/2279_2.png) [@Inforista](https://erlangforums.com/u/Inforista)\ **Post date:** [February 27, 2024, 4:41pm UTC](https://erlangforums.com/t/is-lookup-and-insert-really-constant-time-in-erlang-ets-set/3335/8 "2024-02-27T16:41:06Z")
@sverker thank you for checking up on this 😊 Actually I am working on a new kind of AI and tuplespace information system, where it is highly likely that I will hit this limit (sometime within 1/2-2 years time from now). So If you can add this easy fix, and raise the limit, in a future release I will be very happy πŸ˜ƒ ---
**Author:** ![sverker](https://erlangforums.com/user_avatar/erlangforums.com/sverker/32/841_2.png) [@sverker](https://erlangforums.com/u/sverker)\ **Post date:** [February 27, 2024, 5:19pm UTC](https://erlangforums.com/t/is-lookup-and-insert-really-constant-time-in-erlang-ets-set/3335/9 "2024-02-27T17:19:17Z")
Write an issue at [GitHub - erlang/otp: Erlang/OTP](https://github.com/erlang/otp) so we don’t forget it. ---
**Author:** ![Inforista](https://erlangforums.com/user_avatar/erlangforums.com/inforista/32/2279_2.png) [@Inforista](https://erlangforums.com/u/Inforista)\ **Post date:** [February 27, 2024, 5:20pm UTC](https://erlangforums.com/t/is-lookup-and-insert-really-constant-time-in-erlang-ets-set/3335/10 "2024-02-27T17:20:34Z")
Ok, I will write an official issue at GitHub Erlang/OTP πŸ™‚