java的hashmap源码中是这样实现的，一个数组用来存放key值，根据key的hash值（hash这个值）存储到对应index位置，每个位置从头节点开始，是一个链表，依次把相同key的元素连起来。当遇到相同key的时候就遍历链表进行插入或者查询操作。
这个应该可以满足你的要求吧？

前三个都很好做，但是第四个问题描述得不够清楚，因为可能多个key对应的都是相同的value，所以根据value去获取key就比较麻烦了，结果可能是一个数组。如果保证一一对应，key和value也都是唯一的，那么像楼上说的简单的两棵平衡树就可以解决

一下能想到的是个很二的办法：用两棵树……
没特殊约束的话，说不定我真的会这么实现。