*Lookup layers scale as vocab size increases.
This is supposed to be a performance issue, and I thought I labeled it as such Colab Link which also shows a tensorboard trace, where we don't see anything but IDLE time after the lookup
https://colab.research.google.com/drive/1W7_VLsGW-pfW2FVpAuRqECTaEFEmalwf?usp=sharing Looks to be specific to keras
![image](https://user-images.githubusercontent.com/43187008/232564564-1443c1c1-e19b-4c2d-9e0e-7834c7761c53.png)

Lots of python calls that scale with size. @sboshin, Apologies for the delay. I was able to replicate the issue in Colab using Tensorflow 2.11, 2.12 and tf-nightly. Please check the gists for the same [2.11](https://colab.sandbox.google.com/gist/synandi/4606f64fe51cb02867ba50efd5bd9a70/60339_2-11.ipynb), [2.12](https://colab.sandbox.google.com/gist/synandi/f036b3d0219dada668830f88a1c3a015/60339_2-12.ipynb) and [tf-nightly(2.13.0.dev20230418)](https://colab.sandbox.google.com/gist/synandi/2639d691a5c62bba8ef30ea7fa639618/60339_nightly.ipynb). 

This seems to be a keras issue. Please post this issue on [keras-team/keras repo.](https://github.com/keras-team/keras/issues)
To know more see;
[https://discuss.tensorflow.org/t/keras-project-moved-to-new-repository-in-https-github-com-keras-team-keras/1999](https://discuss.tensorflow.org/t/keras-project-moved-to-new-repository-in-https-github-com-keras-team-keras/1999).Thanks!"	
Thank you!  I was able to replicate this issue directly with statichash tables, so I don't think this is a keras issue. 
Ill update the colab with using statichash operator directly. Hi @sboshin ,

Increase on `vocabulary_size` makes the hash table bigger and time complexity may increases for worst case right ? I can see in worst case the time complexity can be O(n) as well as per the [source](https://en.wikipedia.org/wiki/Hash_table). 

Also here we are comparing time complexity of two different hash tables of different sizes. IMO, normally we compare time complexity of different operations on same table. For example I have tested each table with 3 different search operations and the time is almost same for each hash table first table around 70 ms per loop and second table around 850 µs per loop.

Please refer to attached [gist](https://colab.research.google.com/gist/SuryanarayanaY/d9be111da17510cb66eda50382b2f94b/60339.ipynb). I am confused. The lookup of a hash table should be O(1), and if we claim worst case, we shouldn't hit worst case every time. You have basically shown proof TF hash tables hit the worst case, every time.
 > Also here we are comparing time complexity of two different hash tables of different sizes. IMO, normally we compare time complexity of different operations on same table. For example I have tested each table with 3 different search operations and the time is almost same for each hash table first table around 70 ms per loop and second table around 850 µs per loop.

How else would you check the time complexity of a hash table by size? 
@synandi Is this also your opinion?
Do TF hash table lookup operations always O(n). As per "source" we also see, average case should be O(1), How can you tell me this is the average case? Worst case should be rare not all the time. 

A worst case scenario occurs when you have constant collisions because the hash function is bad, so you are either claiming TF hash function is terrible or there is still a bug causing it to take O(n)

Lookup is to take a key, hash it to its location that is a constant time complexity, and it shouldn't scale with vocab size.
 ![image](https://user-images.githubusercontent.com/43187008/235731519-ce98bb0f-279e-4e48-a2ec-3bdc834be992.png)

Might as well use a dictionary.
<details><summary>Click to expand!</summary> 
 
 ### Issue Type

Performance

### Have you reproduced the bug with TF nightly?

Yes

### Source

binary

### Tensorflow Version

v2.11.0-rc2-17-gd5b57ca93e5 2.11.0

### Custom Code

No

### OS Platform and Distribution

os platform: Linux-4.19.0-23-cloud-amd64-x86_64-with-debian-10.13 linux distribution: ('debian', '10.13', '')

### Mobile device

_No response_

### Python version

python version: 3.7.12

### Bazel version

_No response_

### GCC/Compiler version

_No response_

### CUDA/cuDNN version

NVIDIA-SMI 460.32.03    Driver Version: 460.32.03    CUDA Version: 11.2   

### GPU model and memory

_No response_

### Current Behaviour?

String/IntegerLookup layers underneath use the statichashtable. 
I have noticed as the vocab size increases, performance decreases, as I assumed it was basically a hash table with a O(1) lookup time, this shouldn't be the case. Is my assumption wrong on the time complexity?

### Standalone code to reproduce the issue

```shell
test = tf.keras.layers.StringLookup(name=f"{100000}_string_lookup", vocabulary = list(map(str, range(100000))))
%timeit test("23")
>> 75.3 ms ± 430 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

test_100 = tf.keras.layers.StringLookup(name=f"{100}_string_lookup", vocabulary = list(map(str, range(100))))
%timeit test_10("23")
>> 610 µs ± 21.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

testi = tf.keras.layers.IntegerLookup(name=f"{100000}_int_lookup", vocabulary = list(range(100000)))
testi_100 = tf.keras.layers.IntegerLookup(name=f"{100}_string_lookup", vocabulary = list(range(100)))

%timeit testi(23)
%timeit testi_100(23)

>>75.9 ms ± 421 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
>>816 µs ± 21.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
```


### Relevant log output

```shell
75.3 ms ± 430 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
610 µs ± 21.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

75.9 ms ± 421 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
816 µs ± 21.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
```
</details>