J-uby, 29 bytes

Takes a Hash, returns an array of key-value pairs.

:zip%[:keys,:values|:shuffle]

Attempt This Online!

J-uby, 33 bytes

Takes a Hash, returns a Hash.

(:zip|H)%[:keys,:values|:shuffle]

Attempt This Online!

Swift 5.9, 65 bytes

let f={(k:[(Int,Int)])in[]+zip(k.map(\.0),k.map(\.1).shuffled())}

Takes input as an Array of tuples, because I'd have to convert a native Dictionary into an array of tuples anyway.

Python 3, 39 bytes

lambda d:{i:d[s]for i,s in zip(d,{*d})}

Try it online!

This works because string hashes are randomized in Python.

Python, 73 70 bytes

-3 thanks to @tsh

lambda d:dict(zip(d,sample([*d.values()],len(d))))
from random import*

Attempt This Online!

Pretty straightforward. I think this is valid Python 3.5 (available at the time of the OP).

Wolfram Language (Mathematica), 26 bytes

RandomSample~SubsetMap~All

Try it online!

Input an Association, Mathematica's built-in mapping type.

Since SubsetMap acts on a List of values of the subset, keys stay in place while values are shuffled. For some reason, it seems like SubsetMap does not consider ;; a valid Span of all elements, so we use All instead.

SubsetMap was introduced in 2019 (v12.0), postdating this challenge.

JavaScript (Node.js), 70 bytes

f=a=>a[b=1/Math.random()|0]?f(a,t=a[b][1],a[b][1]=a[0][1],a[0][1]=t):a

Try it online!

Java 7, 156 bytes

import java.util.*;void c(Map m){List t=new ArrayList(m.values());Collections.shuffle(t);Iterator i=t.iterator();for(Object k:m.keySet())m.put(k,i.next());}

Ungolfed:

void c(Map m){
  List t = new ArrayList(m.values());
  Collections.shuffle(t);
  Iterator i = t.iterator();
  for(Object k : m.keySet()){
    m.put(k, i.next());
  }
}

Test code:

Try it here.

import java.util.*;
class M{
  static void c(Map m){List t=new ArrayList(m.values());Collections.shuffle(t);Iterator i=t.iterator();for(Object k:m.keySet())m.put(k,i.next());}
  
  public static void main(String[]a){
    for(int i=0;i<10;i++){
      Map m=new HashMap();
      m.put(0, 10);
      m.put(1, 10);
      m.put(5, 5);
      c(m);
      System.out.println(m);
    }
  }
}

Possible output:

{0=5, 1=10, 5=10}
{0=10, 1=10, 5=5}
{0=10, 1=5, 5=10}
{0=10, 1=10, 5=5}
{0=10, 1=10, 5=5}
{0=10, 1=10, 5=5}
{0=10, 1=10, 5=5}
{0=10, 1=10, 5=5}
{0=10, 1=5, 5=10}
{0=5, 1=10, 5=10}

R, 47 (28) bytes

A bit late to the party but though I'd post a solution in R using builtins.

The closest thing R has to an array with key/value mapping is a list. The following function takes a list object as input and outputs a list with its values shuffled.

function(x)return(setNames(sample(x),names(x)))

Explained

The builtin setNames() can assign names to objects by inputting a R-vector of names. Hence, first shuffle the list by sample() which shuffles the pairs, and then assign the names in the original order using names().

Example:

z  <- list(fish = 1, dog = 2, cat = 3, monkey = 4, harambe = 69)

f=function(x)return(setNames(sample(x),names(x)))
f(z)

$fish
[1] 3

$dog
[1] 1

$cat
[1] 2

$monkey
[1] 69

$harambe
[1] 4

If x is assumed to be defined there's no need for function wrapping and the program reduces to 28 bytes.

setNames(sample(x),names(x))

Perl 6, 28 bytes

{%(.keys.pick(*)Z=>.values)}

Input is a Hash
( Technically any value with a .keys method and a .values method would work, but the output is a Hash )

Explanation:

# bare block lambda with implicit parameter ｢$_｣
{

  # turn the list of key => value Pairs into a Hash
  %(
      # get the keys from ｢$_｣ ( implicit method call on ｢$_｣ )
      .keys

      # get all of the keys in random order
      .pick(*)

    # zip using ｢&infix:« => »｣ the Pair constructor
    Z[=>]

      # the values from ｢$_｣ ( implicit method call on ｢$_｣ )
      .values
  )
}

A variant that would work for the other built in Hash like object types is:

{.WHAT.(.keys.pick(*)Z=>.values)}

.WHAT on an object returns the type.

Clojure, 40 34 bytes

#(zipmap(keys %)(shuffle(vals %)))

Takes the keys and values from m (a map), shuffles the values and zips them up into a map.

JavaScript (ES6), 89 bytes

a=>a.map((_,i)=>[i,Math.random()]).sort((a,b)=>a[1]-b[1]).map(([i],j)=>[a[j][0],a[i][1]])

php, 84 bytes

<?= serialise(array_combine(array_keys($a=unserialize($argv[1])),shuffle($a)?$a:0));

Takes input as a serialised array, outputs the same.

Perl, 35 bytes

Includes +2 for -0p

Give each keys/value separated by space on a STDIN line

shuffle.pl
1 5
3 8
9 2
^D

shuffle.pl:

#!/usr/bin/perl -p0
@F=/ .*/g;s//splice@F,rand@F,1/eg

Python 3, 107 bytes

Uses Python's native dictionary structure.

Thanks to @mbomb007 for saving a byte.

from random import*
def f(d,o={}):
 i=list(d.values());shuffle(i)
 for k in d.keys():o[k]=i.pop()
 return o

Ideone it!

Python 2, 77 bytes

Uses this option: If you input an array or a map, you can modify the original object instead of returning. Input is a dictionary literal like {0: 10, 1: 10, 5: 5}.

from random import*
D=input()
k=D.keys()
shuffle(k)
D=dict(zip(k,D.values()))

Try it online

Inspiration taken from this SO answer.

PowerShell v2+, 52 bytes

param($a)$a|%{$_[1]}|sort {random}|%{$a[$i++][0],$_}

Takes input as an array of tuples, which is significantly shorter than using a hash (which would require .GetEnumerator() and whatnot to work).

We loop the input array |%{...}, each iteration pulling out the second element $_[1]. Those are piped into Sort-Object with the {Get-Random} as the sorting key. This will assign a random weight from 0 to [Int32]::MaxValue to each element for sorting. Those are piped into another loop |%{...}, with each iteration outputting a tuple of the corresponding first element of the tuple and the sorted number.

Examples

The examples here have an additional -join',' on the tuple output so it's shown better on the console, as the default output for multi-dimensional arrays is hard to read.

PS C:\Tools\Scripts\golfing> .\shuffle-a-mapping.ps1 ((0,10),(1,10),(5,5))
0,10
1,5
5,10

PS C:\Tools\Scripts\golfing> .\shuffle-a-mapping.ps1 ((0,10),(1,10),(5,5))
0,10
1,10
5,5

PS C:\Tools\Scripts\golfing> .\shuffle-a-mapping.ps1 ((1,1),(2,2),(3,3),(4,4),(5,5))
1,2
2,4
3,3
4,5
5,1

This works for non-integer values as well with no modifications.

PS C:\Tools\Scripts\golfing> .\shuffle-a-mapping.ps1 (('one','one'),('two','two'),('three','three'),('four','four'))
one,four
two,three
three,two
four,one

Jelly, 5 bytes

Ṫ€Ẋṭ"

Try it online!

Explanation

Ṫ€Ẋṭ"  Input: list of [k, v] pairs
Ṫ€     Pop and return the last element of each k-v pair (modifies each list)
  Ẋ    Shuffle the list of v's
   ṭ"  Append each v back to a k and return

CJam, 9 bytes

{z)mra+z}

Input is a list of key-value pairs.

Test it here.

Explanation

z  e# Zip, to separate keys from values.
)  e# Pull off values.
mr e# Shuffle them.
a+ e# Append them to the array again.
z  e# Zip, to restore key-value pairs.

Alternative solution, same byte count:

{[z~mr]z}

Brachylog, 13 12 bytes

zt@~T,?zh:Tz

Try it online!

Expects a list of 2-element lists as input.

Explanation

z              Zip the input to get a list of keys and a list of values
 t@~T,         Take the list of values, and shuffle it ; call that T
      ?zh      Zip the input to get the list of keys
         :Tz   Zip the list of keys with the list of shuffled values

Mathematica, 32 bytes

{#,RandomSample@#2}&@@(#)&

Input is a list of key-value pairs.  is Mathematica's transposition operator, and RandomSample can be used to shuffle a list.

05AB1E, 5 bytes

Input is a list of key-value pairs.

ø       # zip into a list of keys and one of values
 `      # flatten
  .r    # randomize the values
    ø   # zip back again into a list of key-value pairs.

Try it online!