def format_keys(d, format_string):
    """
    Creates a new dict with all keys from an original dict reformatted/mapped.

    :param d: a dict.
    :param format_string: a normal python format string (i.e. str().format() style).
    :return: a new dict (of the same type as the original) containing the original dict's values,
        but with each key reformatted (as a string).

    >>> format_keys({'a': 1, 'b': 2}, '#{}:')
    {'#b:': 2, '#a:': 1}

    >>> format_keys(OrderedDict([('a',  1), ('z',  26)]), 'K={}.')
    OrderedDict([('K=a.', 1), ('K=z.', 26)])
    """
    dict_type = type(d)
    d = dict_type([(format_string.format(k), v) for k, v in d.items()])
    return d