Object put(Object key, Object value)
    throws IOException {
        if (value == null) {
            return remove(key);
        }
        int hash = hashCode(key);
        long child_recid = _children[hash];
        if (child_recid == 0) {
            // no bucket/page here yet, let's create a bucket
            HashBucket bucket = new HashBucket(_depth+1);

            // insert (key,value) pair in bucket
            Object existing = bucket.addElement(key, value);

            long b_recid = _recman.insert(bucket);
            _children[hash] = b_recid;

            _recman.update(_recid, this);

            // System.out.println("Added: "+bucket);
            return existing;
        } else {
            HashNode node = (HashNode) _recman.fetch( child_recid );

            if ( node instanceof HashDirectory ) {
                // recursive insert in next directory level
                HashDirectory dir = (HashDirectory) node;
                dir.setPersistenceContext( _recman, child_recid );
                return dir.put( key, value );
            } else {
                // node is a bucket
                HashBucket bucket = (HashBucket)node;
                if (bucket.hasRoom()) {
                    Object existing = bucket.addElement(key, value);
                    _recman.update(child_recid, bucket);
                    // System.out.println("Added: "+bucket);
                    return existing;
                } else {
                    // overflow, so create a new directory
                    if (_depth == MAX_DEPTH) {
                        throw new RuntimeException( "Cannot create deeper directory. "
                                                    + "Depth=" + _depth );
                    }
                    HashDirectory dir = new HashDirectory( (byte) (_depth+1) );
                    long dir_recid = _recman.insert( dir );
                    dir.setPersistenceContext( _recman, dir_recid );

                    _children[hash] = dir_recid;
                    _recman.update( _recid, this );

                    // discard overflown bucket
                    _recman.delete( child_recid );

                    // migrate existing bucket elements
                    ArrayList keys = bucket.getKeys();
                    ArrayList values = bucket.getValues();
                    int entries = keys.size();
                    for ( int i=0; i<entries; i++ ) {
                        dir.put( keys.get( i ), values.get( i ) );
                    }

                    // (finally!) insert new element
                    return dir.put( key, value );
                }
            }
        }
    }