write a class which can have two array list.one to store key and another to store value. use some indexing algorithm, to make good performance.

Instead of using 2 lists; which could make synchronizing (when adding/removing) these lists an overhead you could use a 2 dimensional array.