Is there any index with O(1) complexity for lookup in PostgreSQL?

You'll need to the read the PostgresSQL Index Types documentation for the version that you are using. I think you are looking for a Hash Index, but as as the documentation explains the real world performance and pros and cons depend on the implementation details and recommendations of the particular version that you are using.

I don't think anything, even hash indexes, are going to guarantee a O(1).

• This would only be achievable when asking for specific entries where x = 'a' or sets where x in ('a','b')
• Hash tables achieve O(1) by an array of "buckets" corresponding to a hash value each. On the other hand, if we're talking of only storing the values, and not the empty buckets, this is essentially the same lookup characteristics as a balanced b-tree.
• I've read somewhere that (in pg) hash index lookups "perform [as/no better than] b-tree indexes" or something like that, which indicates it's not stored with empty buckets.
• The penalty for a O(log(N)) over a O(1) lookup is easily dwarfed by the overhead of sending it to the db and waiting for the result in the first place.

One way in which a hash index can improve performance over a b-tree index is by hashing it to a smaller, fixed-size piece of data.

However, from the docs for the newest version (9.1):

Caution

Hash index operations are not presently WAL-logged, so hash indexes might need to be rebuilt with REINDEX after a database crash. They are also not replicated over streaming or file-based replication. For these reasons, hash index use is presently discouraged.