Consider a hashmap. Hashmaps give expected constant access time, and amortised constant access time on the condition that their size grows at a sufficient rate and that the hash function is a universal hashing function. This is parametric.

Assume that you use a linkedlist for collisions, then for some growth rates, your cost of access is not constant, and becomes linear to your input.